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

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 (\large \sum et \large \prod interdits !) permettant de calculer une approximation de cet exposant ?

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

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.

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 :) )

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 ;) )

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 :
n=pq+r avec 0 \leq r <p
q=pq'+r' avec 0 \leq r' <p
donc
n = p(pq'+r')+r = p^2q'+pr'+r

On a donc q' est le quotient de n par p² à condition que 0 \leq pr'+r <p^2.
Or je trouve : 0 \leq pr'+r <p^2+p.

Où est mon erreur... ?

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

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 !

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

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

oui, c'est ça

D'accord, merci...

Maintenant, pour la deuxième question, je dirais qu'on élimine les restes soit :
n=pq
q=pq'
donc
n = p(pq') = p^2q'

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é...

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...

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.

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.

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.

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

n=pq+r_0 avec 0 \leq r_0 <p
q=pq_0+r_1 avec 0 \leq r_1 <p
\vdots
q_{m-1}=pq_m+r_{m+1} avec 0 \leq r_{m+1} <p

donc
n = p^{m+1}q_{m-1}+p^mr_m+...+pr_1+r_0 avec 0 \leq p^mr_m+...+pr_1+r_0 <p^{m+1}

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

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 pi, alors le quotient de q par p est le quotient de n par pi+1

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 pi+1 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)

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 pi, alors le quotient de q par p est le quotient de n par pi+1
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 ;)

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

n=pq+r_0 avec 0 \leq r_0 <p
q=pq_0+r_1 avec 0 \leq r_1 <p
\vdots
q_{m-1}=pq_m+r_{m+1} avec 0 \leq r_{m+1} <p

donc
n = p^{m+1}q_{m-1}+p^mr_m+...+pr_1+r_0 avec 0 \leq p^mr_m+...+pr_1+r_0 <p^{m+1}

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...