[Maths] [TS] Exercice d'arithmétique - Forum Exercices pour les concours et examens

g_h · 05/05/2005, 12h29

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

kron · 05/05/2005, 14h16

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

g_h · 05/05/2005, 14h18

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.

g_h · 05/05/2005, 16h57

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

)

martini_bird · 06/05/2005, 14h49

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

)

Antikhippe · 14/05/2005, 10h50

Salut,

Citation:

Posté par martini_bird

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

g_h · 14/05/2005, 11h04

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

Antikhippe · 14/05/2005, 11h21

Citation:

Posté par g_h

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 !

**matthias** · 14/05/2005, 11h57

Citation:

Posté par Antikhippe

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

Antikhippe · 14/05/2005, 12h04

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

g_h · 14/05/2005, 12h06

oui, c'est ça

Antikhippe · 14/05/2005, 12h20

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

Antikhippe · 14/05/2005, 12h22

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

**matthias** · 14/05/2005, 12h25

Citation:

Posté par Antikhippe

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.

**matthias** · 14/05/2005, 12h33

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.

g_h · 14/05/2005, 12h40

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.

Antikhippe · 14/05/2005, 13h41

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

g_h · 14/05/2005, 15h41

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)