Un faux petit théorème de Fermat

Bonjour,

Peut-être assez connu mais intéressant je trouve :

Trouvez tous les entiers n tels que pour tout entier a

a^{n+1} = a (mod n).

lolo

n=0 solution
soit n>=1, le logarithme discret me semble servir à donner des solutions

je sais pas bien ce qu'est le logarithme discret ?

Sinon il faut regarder quels sont les facteurs premiers possible de n.

lolo

Soit le groupe cyclique Z_p* d'ordre p − 1 et de générateur g. Étant donné a = b^x mod p,
où x est un entier 0 =< x < p − 1, l’entier x est appelé le logarithme discret de a en base b, et on le note log_b(a).
x est aussi un élément de Z_(p−1).

Merci beaucoup pour la définition ( est-ce que b= g ou je ne vois pas pourquoi g intervient ?).
Sinon comme on utilise la structure de Z/pZ* oui ça doit se faire aussi avec ça.

lolo

n = 1 convient
n > 1 désormais


Si n est divisible par un carré > 1, p², alors p^(n+1) != p [n]
Donc n est libre de carré.

n = ¶ pi, pi premier (i = 1 .. N, pi rangés dans l'ordre croissant)

La condition est donc que pi-1 | n, pour tout i, d'après Fermat (le vrai ce coup-ci !).

n impair est donc impossible : p1 = 2

Si N >= 2 : 2 < p2-1 | n.
Vu que p2 - 1 < p3 on doit avoir p2-1 | p1, i.e. p2 = 3.

si N >= 3 : 3 < p3-1 | n
Pareil on doit avoir p3-1 | p1·p2, p3 = 7 seule possibilité.

Si N >= 4 : p4-1 | p1·p2·p3 = 42 : pas de solution.


Les seules solutions sont donc : 2, 2·3, 2·3·7


—————————————
bizarre qu'il y ait si peu de solutions

p4 = 43 ?

Euh oui .....

Sauf erreur, une fois de plus, cela s'arrête là

oui tout à fait bravo !