Question sur l'indicateur d'Euler

[Reihan]

Bonjour à tous;
On sait tous que si un entier n est premier, alors φ(n)=n-1
On m'a demandé de trouver une démonstration pour la réciproque de cette propriété :
Soit n un entier et φ(n)=n-1,démontrer que n est forcément premier.

Merci beaucoup
Cordialement

[Ben314]

Salut,
C'est quoi la définition de phi(n) ?
- Soit tu la connait et le résultat que tu as à démontrer est totalement évident.
- Soit tu la connais pas et je t'inciterais fortement à éviter de manipuler des truc dont tu ne connais absolument rien : ça pourrait très bien te "péter à la g..." par exemple...

[Reihan]

la définition de phi(n):Le nombre des entier inférieur à n et premier avec lui(pgcd =1).
donc quand n est un nombre premier puisque son PGCD est 1 avec tous les nombres inférieur à lui donc le nombre des entiers inférieur à lui et premier avec lui et n-1.Ca c'est évident
mais la réciproque nous dit qui si phi(n)=n-1 ,alors n est un nombre premier.
il faut la prouver et on ne peut pas dire que c'est évident.(c'est ce qu'on m'a dit).
désolée pour les fautes de Français je ne suis pas francophone.

[zygomatique]

salut

alors peut-être faudrait-il savoir aussi ce que sont deux nombres premiers entre eux ....

[Reihan]

deux nombre sont dit premiers entre eux si leur PGCD = 1.
ca je sais mais je n'arrive pas à faire la démonstration souhaitée.

[zygomatique]

super .... et qu'est-ce que ça veut dire que leur pgcd est 1 ?


franchement :: que peut-on dire d'un entier n si les n - 1 entiers qui le précèdent sont premiers avec lui ...

voir crible d'Eratosthène ....

[Reihan]

c'est à dire qu'l n'ont pas de facteur commun.
oui , c'est vrai ce que vous dite.
mais enfaite la démonstration qu'elle à fait pour un nombre n c'était comme ca:
soit n un entier composé de deux facteur premier p et q
n=pq si phi(n)=n-1 alors on a phi(n)=pq-1 comme p et q sont premier phi(n)=(p-1)(q-1)=pq+1-p-q ->
pq+1-p-q=pq-1
2=p+q impossible
donc n est forcément premier.
ici on l'a démontré pour 2 facteurs premiers.
maintenait elle me demand de le faire pour n facteurs premiers.

[zygomatique]

et comment on sait que ::

comme p et q sont premier phi(n)=(p-1)(q-1)

[Reihan]

on a déjà accepté que si n est un nombre premier alors phi(n)=n-1
on veut démontrer la réciproque.

[Reihan]

et on sait aussi que si n=pq
phi(n)=phi(p)phi(q)

[Lostounet]

Salut,
Pourquoi se fatiguer à démontrer ... une conséquence immédiate de la définition?

Supposons: Soit n > 1 tel que: phi(n) = n - 1

Montrons que n est premier, c'est à dire que n admet exactement deux diviseurs distincts (n et 1).

On sait que phi(n) = Card{k / k<n, k premier avec n} = nombre d'entiers k < n tels que pgcd(k, n) = 1

Dire phi (n) = n -1 <=> il existe n - 1 entiers inférieurs à n tels qu'ils soient premiers avec n.
Cela signifie exactement que n n'admet aucun diviseurs parmi tous les nombres qui lui sont inférieurs, sauf le nombre 1.

Donc n est un nombre premier.

[Ben314]

la définition de phi(n):Le nombre des entier inférieur à n et premier avec lui(pgcd =1).
donc quand n est un nombre premier puisque son PGCD est 1 avec tous les nombres inférieur à lui donc le nombre des entiers inférieur à lui et premier avec lui et n-1.Ca c'est évident

Parce que toi, ça te semble pas complètement évident que, si un nombre est premier avec tout ceux qui lui sont inférieur, ça veut dire qu'il est premier.
Je te rappelle (au cas où) que si un nombre N n'est pas premier, c'est qu'il a un diviseur D tel que 1<D<N et que, dans ce cas le pgcd de N et D c'est évidement D et donc surement pas 1.

Et tu pourra à la limite signaler à "celle" qui a commencée la preuve en question en utilisant le fait que phi(pq)=phi(p)phi(q) pour montrer une telle banalité que :
a) C'est vraiment "utiliser un bulldozer pour écraser une mouche".
b) Et qu'en plus ça ne marche pas du tout vu que la formule phi(pq)=phi(p)phi(q) n'est valable que lorsque p et q sont premier entre eux et que, dans le cas où N est le carré d'un nombre premier (par exemple 25=5²), ben t'es pas dans la merde pour écrire N=pq avec p et q premier entre eux...