Artihmétique - Theoriquement abordable en sup

[merwan.r]

Bonsoir à tous, je suis novice sur ce forum, et espère bien qu'il se revèlera d'une grande efficacité :)

J'ai trouvé cet exercice d'oral de l'ENS dans l'ODT, il est supposément abordable en sup, cependant je ne sais vraiment pas comment m'y prendre...

"Montrer que si n divise a^n - b^n alors n divise (a^n-b^n)/(a-b)"

Evidemment j'ai ramené le quotient à étudier à la somme qu'on obtient en factorisant an - bn par a - b (si quelqu'un sait comment noter les sommes sur ce site je suis preneur ) (je note an pour a^n...)

(an - bn) = (a-b)(somme k = 0 ---> k = n - 1 des a^(n-1-k)*b^k)
soit (a-b)(binome de newton jusqu'à n-1 sans les coefficients binomiaux)


Il faudrait donc demontrer que n divise cette somme, j'ai pensé à une eventuelle disjontion des cas selon le fait que n divise ou non (a-b), mais j'ai écarté cette idée, aucun des deux cas ne s'avérant plus simple, la factorisation par (a-b) dans le cas ou n divise a -b est faisable mais fais ressortir des termes de compensation qui si on les factorise font à leur tour ressortir des termes de compensation...


J'ai ensuite pris le probleme de maniere plus globale il faut montrer

(an - bn) = nq ==> (an -bn)(a-b) = nq'
et là franchement je sèche...

En esperant compter sur vous, merci bien !

[wserdx]

Oui en effet, je pense que c'est abordable;
En posant , développe
. Tu trouves une expression où est en facteur. Soit un facteur premier de .
Si ne divise pas , alors il divise l'autre facteur.
Si divise dans l'autre facteur, tous les termes sont multiples de puissances de , (donc divisibles par ), sauf un qui est , mais aussi par hypothèse divisible par .
Faudrait regarder ensuite plus en détail ce qui se passe si est facteur multiple de , mais je te laisse le soin de conclure.

[Ben314]

Bonsoir,
Soit j'ai pas tout compris,... soit c'est un peu faux.

Si ne divise pas , alors il divise l'autre facteur.

Le nombre 6 divise 4x9, ne divise pas 4,... et ne divise pas non plus l'autre facteur...

...des coefficients binomiaux tous divisibles par , sauf le coefficient de ...

est tu bien sûr que, par exemple, 6 divise tout les coeff. binomiaux C(6,?) sauf un ( ces coeffs. sont 1, 6, 15, 20, 15, 6, 1...)

[wserdx]

Oui, je suis allé un peu vite, tu as du lire mon message juste avant que je ne le corrige. J'ai remplacé par , facteur premier de .

[wserdx]

Bon, désolé, ça doit être un peu faux. Je vérifie mes calculs... :marteau:

[merwan.r]

Ouaïe la claque, indeed vu comme ça ça se fait facilement, écoute je te remercie grandement, je sais pas si tu l'avais déjà fait mais sinon, qui que tu sois, bien joué ! Bonne nuit.

[Ben314]

Je pense que c'est juste mais... insufisant.
Si dans la décomposition de n en facteurs premiers il y a des carrés, ta preuve ne prouve pas que n divise (a^n-b^n)/(a-b)
Par exemple, si n=180=2².3².5, ta preuve montre seulement que 30=2.3.5. divise (a^n-b^n)/(a-b).

Ca peut peut être marcher en prenant q=p^k (plus grande puissance de p divisant n), en écrivant c=c'p^m (avec c' premier avec p) puis en évaluant les puissances de p qui apparaissent dans chaque terme de la somme (b+c)^n-b^n (une fois développée)...

[Ben314]

Je suis aussi en train de voir que, le gros problème dans ta preuve, c'est qu'il me semble que tu n'utilise pas trop l'hypothèse.........

[Ben314]

Ton idée marche peut être quand même.
On suppose que divise et on veut montrer que divise aussi .
Pour cela, il suffit de montrer que, pour tout (avec premier et ) apparaissant dans la décomposition en nombre premier de on a : .

Si n'est pas divisible pas par alors il est premier avec et comme (car par hypothèse ) et on peut en déduire que c'est à dire que .

Si est divisible par , on peut essayer de voir si tout les termes de la somme son bien divisiple par .
Comme est divisible par , il suffit de montrer que est divisible par (avec l'hypothèse que n est divisible par )
Cela semble... trés plausible...

[wserdx]

Oui, j'arrive à la même conclusion, et ce n'est pas si évident que ça à démontrer. J'ai vérifié le résultat expérimentalement pour un petit nombre de valeurs.
Je crois que pour finir il faut compter combien de fois apparait un facteur premier dans une factorielle (et ensuite dans un coefficient binomial)
Par exemple si est premier, apparait fois dans

[Ben314]

C'est exactement ça.
Si tu veux un 'terme technique', le nombre de fois que le facteur apparait dans la décomposition d'un entier non nul s'appele la 'valuation p-adique' de et se note .
On a alors pour tout entier : où désigne la partie entière (la somme est en fait finie...)
Cela donne en particulier ton résultat.
On peut aussi exprimer la valuation p-adique des coeff binomiaux et je pense qu'on peut vérifier que, si divise alors divise les coeff binomiaux pour .

Soit dit en passant, la méthode doit marcher, mais... je la trouve trés "laide" (c'est du gros bourrin) et je demande s'il n'y aurait pas plus simple (ou, plus "joli"), par exemple en utilisant l'indicatrice d'euler (sauf que je sais pas du tout si c'est vu en sup...)

[Doraki]

1) Si p est premier alors a^(p^k) = b^(p^k) mod p^k <=> a = b mod p.

2) Si p est premier et a^p - b^p = 0 mod p alors p divise (a^p - b^p)/(a-b).

Sachant ces deux résultats on peut résoudre le problème par récurrence :
C'est vrai si n=1.
On suppose que n divise a^n - b^n, et que n = p*m où p est premier.
En appliquant 2) sur a^m et b^m on en déduit que p divise (a^n - b^n)/(a^m - b^m)
On montre avec 1) et le théorème des restes chinois que m divise a^m - b^m.
L'hypothèse de récurrence avec m dit que m divise (a^m - b^m) / (a-b).
Donc n = p*m divise (a^n - b^n) / (a-b).

[Ben314]

...p divise (a^n - b^n)/(a^m - b^m)...
...m divise (a^m - b^m) / (a-b)....
Donc p*m divise (a^n - b^n) / (a-b).

Ne faudrait il pas que p et m soient premier entre eux ?

Sinon, l'idée me parrait bien plus jolie, et je pense que ça marche modulo le fait que :
a=p [mod p] => a^(p^k)=b^(p^k) [mod p^(k+1)]

[yos]

Le résultat est évident si n=p (premier). Il est pas trop dur si n= (mais là j'utilise le théorème d'Euler).
Ensuite on l'a par récurrence sur l'exposant :
si pour tout entier , on a l'implication voulue, on regarde le cas de l'exposant N+1; s'il est primaire c'est OK, sinon il s'écrit nm avec n et m premiers entre eux et .
.
Le premier facteur est multiple de m par HR donc le premier membre aussi.
Symétriquement, il est multiple de n.
Donc il est multiple de N+1.