[Maths] [TS] Exercice d'arithmétique

[invite97a92052]

Bonjour,

Je venais apporter ma pierre à l'édifice en vous proposant un petit problème (il y a de quoi chercher quand même), qui s'adresse surtout aux terminales :
je n'ai pas pu poster dans le forum "révisions" (même si ce problème n'est pas en rapport direct avec le programme de TS), donc je poste ici, si un modérateur veut bien déplacer le sujet, merci


On m'a donné (en cours de spé) le problème tel quel :

1) (piste pour la suite)
Soient n, p, q, q' des entiers naturels
(Je parle ici de division euclidienne)
Démontrez que si q est le quotient de n par p, et q' le quotient de q par p, alors q' est le quotient de n par p².

2) Comment calculer l'exposant du nombre premier p dans la décomposition en facteurs premiers du nombre n! (factorielle n) ? (avec p < n bien entendu)
Essayez d'élaborer une fonction itérative ou récursive (la récursion rend mieux compte du problème je trouve), qui soit par exemple programmable sur une calculette, permettant de calculer la valeur de cet exposant

3) Saurez-vous trouver une formule ( et interdits !) permettant de calculer une approximation de cet exposant ?
-----

[invite4b9cdbca]

Hehe je n'ai pas fait spé maths, mais je vais chercher, avec un peu de temps je finirai par trouver ^^
Allé déjà on commence par potasser l'arithmétique des cours de spé...

Kron

[invite97a92052]

Ce n'est pas un vrai exo de spé, ici il suffit de savoir ce qu'est une division euclidienne, le reste c'est juste du raisonnement, aucun résultat de cours.

[invite97a92052]

Suites à des remarques de martini_bird (merci !), j'ajouterai qu'à la question 2), si vous faites une fonction il faut la faire de telle sorte que le nombre d'itérations/récursions soit le plus petit possible (il ne faut pas diviser par p tant que le reste est nul, ça serait trop facile )

[A voir en vidéo sur Futura]

[invite4793db90]

Bonjour,

j'ai déplacé le fil et je reproduis le sujet ci-dessous avec une ou deux modifications:

1- Soient n, p, q, q' des entiers naturels.
Démontrer que si q est le quotient de la division euclidienne de n par p, et q' le quotient de q par p, alors q' est le quotient de n par p².

2- Comment calculer l'exposant d'un nombre premier p (p<n) dans la décomposition en facteurs premiers du nombre n! (s'inspirer de la question précédente)?

3- Rédiger un algorithme programmable sur une calculette (ou un ordinateur), permettant de calculer rapidement la valeur de cet exposant. (Question subsidiaire: combien d'opérations sont nécessaires pour un entier n donné?)

4- Donner une formule simple permettant de calculer une approximation de cet exposant?

Merci à g_h!
_____________________

Pour ceux qui sont intéressés, cette exercice peut constituer un point de départ pour démontrer un résultat de Tchebycheff sur la répartition des nombres premiers. (contactez-moi par mp )

[invite39dcaf7a]

Salut,

1- Soient n, p, q, q' des entiers naturels.
Démontrer que si q est le quotient de la division euclidienne de n par p, et q' le quotient de q par p, alors q' est le quotient de n par p².

Voilà ce que j'ai trouvé pour cette question :
avec
avec
donc


On a donc q' est le quotient de n par p² à condition que
Or je trouve :

Où est mon erreur... ?

[invite97a92052]

Il n'y a pas d'erreur, le résultat trouvé est juste, mais il n'y a pas d'équivalence stricte entre ce dont tu es parti et ce à quoi tu arrives : tu as perdu des informations au fil de tes calculs.

Pourquoi ? N'oublie pas que tu travaille avec des entiers naturels, ça te permet de réécrire les inégalités d'une autre façon

[invite39dcaf7a]

N'oublie pas que tu travaille avec des entiers naturels, ça te permet de réécrire les inégalités d'une autre façon

Hmmm... Je ne vois pas ce que ça change...

Merci de m'aider en tout cas !

[invitec314d025]

Hmmm... Je ne vois pas ce que ça change...

Merci de m'aider en tout cas !

Le même problème en plus simple:
Tu prends 4 entiers naturels a,b,x,y tels que:
a<x
b<y
Montrer que a+b<x+y-1

[invite39dcaf7a]

Ah d'accord... c'est à cause des inégalités fortes alors... c'est ça ?

[invite97a92052]

oui, c'est ça

[invite39dcaf7a]

D'accord, merci...

Maintenant, pour la deuxième question, je dirais qu'on élimine les restes soit :


donc


On a donc q' est le quotient de n par p² soit n=p²q'.

En fait, je dirais que pour trouver l'exposant e du nombre premier p de n!, il faut diviser n! x fois jusqu'à trouver un nombre décimal. Ainsi, e=x-1.

Je ne sais pas si c'est bien rédigé...

[invite39dcaf7a]

Au fait, je ne sais pas ce qu'est une fonction récursive (un rapport avec la récurrence peut-être, donc f(Un)=... C'est ça qu'il faut chercher pour f ?).

Je pense que j'ai travaillé avec une fonction itérative, plutôt...

[invitec314d025]

Au fait, je ne sais pas ce qu'est une fonction récursive (un rapport avec la récurrence peut-être, donc f(Un)=... C'est ça qu'il faut chercher pour f ?).

Je pense que j'ai travaillé avec une fonction itérative, plutôt...

En informatique, une fonction récursive est une fonction qui s'appelle elle-même.

[invitec314d025]

Exemple classique, pour caluler n!

factorielle(n)
{
si n=0, résultat = 1
sinon résultat = n*factorielle(n-1)
}

Il faut surtout faire attention à avoir une condition d'arrêt.

[invite97a92052]

Pourquoi "élimines" tu les restes ? Ils ne sont pas forcément nuls ! Tu peux arriver à la conclusion que q' est le quotient de n par p² sans les "éliminer"

De plus, la première question n'est qu'un indice, il faut ensuite passer au cas général (pour tout exposant) pour trouver ce que l'on cherche.

Sinon la méthode que tu propose marche bien, mais elle n'est pas optimale.

Par exemple, pour trouver l'exposant de 5 dans la décomposition en facteurs premiers de 10000!, il suffit de... 5 appels récursifs à la fonction que l'on recherche.
Pour trouver cette fonction, il faut avoir bien compris les implications de la première question.

[invite39dcaf7a]

Généralisation de la première question :

avec
avec

avec

donc
avec

Est-ce-que je me suis trompé dans les indices ou les exposants... ?

[invite97a92052]

C'est sûrement juste, mais ça se servira pas pour la suite (j'avoue que c'est pas évident de voir ou il faut en venir, et c'est fait pour)

en fait, ce qui est intéressant, c'est de montrer que si q le quotient de n par pⁱ, alors le quotient de q par p est le quotient de n par pⁱ⁺¹

De là tu peux tirer quelque chose (une relation récurrente) qui t'aidera pour la suite, où il faudra calculer le quotient de n par pⁱ⁺¹ connaissant q... mais j'en ai peut-être trop dit

Pour la suite, n'oublie pas qu'une factorielle est le produit de tous les entiers consécutifs de 1 à n (ça paraît évident, je sais, mais c'est capital)

[invitec314d025]

C'est sûrement juste, mais ça se servira pas pour la suite (j'avoue que c'est pas évident de voir ou il faut en venir, et c'est fait pour)

en fait, ce qui est intéressant, c'est de montrer que si q le quotient de n par pⁱ, alors le quotient de q par p est le quotient de n par pⁱ⁺¹

C'est à peu près ce qu'Antikhippe a fait. En moins clair et en plus compliqué c'est vrai.
Juste une petite récurrence, ça passera mieux

[invitea3eb043e]

Généralisation de la première question :

avec
avec

avec

donc
avec

Est-ce-que je me suis trompé dans les indices ou les exposants... ?

Au lieu d'écrire que le reste est strictement inférieur au diviseur, essaie d'écrire qu'il est inférieur ou égal au diviseur - 1. Tu verras...

[invite89e47f89]

n=p*q+r1
q=p*q'+r2

n=p^2 * q' + p*r2 +r1 pour monter que q' est le quotient de n par p^2 il suffit de monter que : p*r2+r1 < p^2 .

p > r1 et p > r2 <===> r1 < p et r2 <= p-1
===> p*r2+r1 < p* ( p-1) + p
===> p*r2+r1 < p^2 - p + p
===> p*r2+r1 < p^2

d'ou q' est le quotient de n par p^2


pour la 2 ème question j'ai pas compris la question
si tu veux rediger la question

[invite97a92052]

Pour la 2:

Soit A = n! avec n entier naturel
On a A = n*(n-1)*(n-2)*...*2*1
Mais A peut aussi se décomposer en facteurs premiers :

Exemple, on pose n = 4
A = n! = 4*3*2*1 = 24
Et en facteurs premiers, A = 2³*3

La question est : étant donné un nombre premier p, comment trouver son exposant dans la décomposition en facteurs premiers de A = n!

Exemple pour A = 4!, l'exposant du nombre premier 2 dans la décomposition de A est 3 (2³*3 )

Il faut donc trouver une méthode pour tout nombre premier p et pour tout naturel n, en utilisant impérativement le résultat de la question 1) (interdiction de faire des divisions du nombre A = n!, ce n'est pas du tout efficace)

[invitebc2a6d05]

1) (piste pour la suite)
Soient n, p, q, q' des entiers naturels
(Je parle ici de division euclidienne)
Démontrez que si q est le quotient de n par p, et q' le quotient de q par p, alors q' est le quotient de n par p².

J'ai fait ma terminale S spé Bio (et non maths) en 2003-2004, et venant d'une année de médecine (sans un seul cours de maths) pour me réorienter vers la physique (je ne vais pas non plus vous raconter ma vie... lol), j'ai tenté de résoudre cet exo ou du moins une partie pour me redonner confiance.
Résultat, il me semble avoir trouver assez rapidement la solution du 1. :
q=n/p _ q'=q/p

=> q' = (n/p)/p = n/p²

Par contre pour la suite, vocabulaire inconnu...

[invitec85fb8ec]

Exact !! A quand la suite ?

[invitebc2a6d05]

Exact !! A quand la suite ?

Si ce message est pour moi, je vais répondre:
pour la question 2:
n! = 1*2*...*n (si je me souviens bien)
q = n/p => n = qp

=> n! = 1*2*...*p*...*q*...*qp
et aprés je donne ma langue au chat, ne sachant pas si je suis sur la bonne voie et n'ayant pas étudié ce qu'est une fonction itérative ou récursive (qui doit faire partie du programme de spé je pense).

[invite97a92052]

Résultat, il me semble avoir trouver assez rapidement la solution du 1. :
q=n/p _ q'=q/p

=> q' = (n/p)/p = n/p²

Faux, on parle ici de division euclidienne, et la bonne réponse a été donnée plus haut !

Si ce message est pour moi, je vais répondre:
pour la question 2:
n! = 1*2*...*n (si je me souviens bien)
q = n/p => n = qp

Même remarque, pas de division dans , car n n'est pas divisible par n'importe quoi.

Pour la suite, il faut remarquer que n! = 1*2*3*...*p*...*2p*...*kp*...* (n-1)*n

[invitebc2a6d05]

Dsl
Il me semblait bien qu'il y avait quelque chose qui clochait...
C'est entièrement du programme de spé alors...
Les divisions euclidiennes, je les ai pas vues.
Y a encore plus de pains sur la planche que prévu.

Je vais regarder tous les messages alors...

[invitebc2a6d05]

Pour g_h:
En regardant la première réponse proposée pour la question 1., j'ai essayé de comprendre la division euclidienne.
Si mon analyse est correcte une division euclidienne ne se traduit en écriture mathématique par une division mais plutôt par une multiplication:
du genre a est le quotient de la division euclidienne de b par c; avec a, b et c entiers naturels (ce qui semble être toujours le cas, au moins des entiers, dans les divisions euclidiennes), alors:
b = ca + r avec 0 r c

Est-ce bien celà???
Merci de m'éclairer

[invite97a92052]

du genre a est le quotient de la division euclidienne de b par c; avec a, b et c entiers naturels (ce qui semble être toujours le cas, au moins des entiers, dans les divisions euclidiennes), alors:
b = ca + r avec 0 r c

Est-ce bien celà???
Merci de m'éclairer

Tu peux très bien raisonner dans , et pas seulement dans pour la division euclidienne.

Sinon je suis d'accord, si ce n'est que c'est plutôt plutôt que

[invitebc2a6d05]

Sinon je suis d'accord, si ce n'est que c'est plutôt plutôt que

Donc, si j'ai bien compris les divisions euclidiennes sont définies dans l'ensemble Z, et 0 r < c