par Axelle » mer. 30 nov. 2016 21:12
Bonsoir.
Je fais appel à vous car je bloque sur un problème sur les nombres de Carmichael (et d'arithmétique en général).
Je vous donne tout de suite l'énoncé :
"1) Soit un entier m supérieur ou égal à 2. Soit k appartenant à Z. On suppose qu'il existe un entier l supérieur ou égal à 1 tel que k^l congru à 1 modulo m.
--> Montrer qu'il existe r appartenant à N* tel que pour tout i appartenant à N on ait : k^i congru à 1 modulo n <--> r divise i. (r est l'ordre modulo k de m)
2) Soit n un entier supérieur ou égal à 2, nombre de Carmichael. On veut montrer que n n'est divisible par le carré d'aucun nombre premier.
Indication : raisonner par l'absurde en supposant qu'il existe deux entiers p et q strictement positifs et p premier, tels que n=p^2*q, poser a = 1+pq.
a) Montrer que a^(n-a) congru à 1 modulo n (indication : exprimer (1+pq)(1-pq))
b) Montrer que p est l'ordre de a modulo n.
c) Conclure.
3) (Question qui n'a rien à voir avec les nombres de Carmichael mais qui est dans l'exercice) : soit a un entier supérieur ou égal à 2, montrer que pour tout k appartenant à N, on a :
PGCD(a ; a^k+a^(k-1)+...+1)=1."
J'ai vraiment du mal pour les premières questions et je ne sais pas du tout comment m'y prendre. Pourriez-vous m'indiquer des pistes de réflexion ?
Merci beaucoup par avance pour vos réponses.
Axelle B.
Bonsoir.
Je fais appel à vous car je bloque sur un problème sur les nombres de Carmichael (et d'arithmétique en général).
Je vous donne tout de suite l'énoncé :
"1) Soit un entier m supérieur ou égal à 2. Soit k appartenant à Z. On suppose qu'il existe un entier l supérieur ou égal à 1 tel que k^l congru à 1 modulo m.
--> Montrer qu'il existe r appartenant à N* tel que pour tout i appartenant à N on ait : k^i congru à 1 modulo n <--> r divise i. (r est l'ordre modulo k de m)
2) Soit n un entier supérieur ou égal à 2, nombre de Carmichael. On veut montrer que n n'est divisible par le carré d'aucun nombre premier.
Indication : raisonner par l'absurde en supposant qu'il existe deux entiers p et q strictement positifs et p premier, tels que n=p^2*q, poser a = 1+pq.
a) Montrer que a^(n-a) congru à 1 modulo n (indication : exprimer (1+pq)(1-pq))
b) Montrer que p est l'ordre de a modulo n.
c) Conclure.
3) (Question qui n'a rien à voir avec les nombres de Carmichael mais qui est dans l'exercice) : soit a un entier supérieur ou égal à 2, montrer que pour tout k appartenant à N, on a :
PGCD(a ; a^k+a^(k-1)+...+1)=1."
J'ai vraiment du mal pour les premières questions et je ne sais pas du tout comment m'y prendre. Pourriez-vous m'indiquer des pistes de réflexion ?
Merci beaucoup par avance pour vos réponses.
Axelle B.
