Le petit théoreme de fermat

A) Le théorème

"Si p est un nombre premier et a un naturel non divisible par p alors a^(p-1)-1 est divisible par p" (autrement dit: a^(p-1)≡1 [p] )

On se propose de démontrer ce théorème.
On note A= {a,2a,3a,....,(p-1)a} = {ka; 1<k<p-1}

a) Justifier que p ne divise aucun élément de A, et que les restes de la division euclidienne des éléments de A par p sont non nuls et distincts.

b)On note P= produit des éléments de A.
-Justifier que p divise P-(p-1)!
-Montrer que P-(p-1)!=(p-1)!(a^(p-1)-1)
-Conclure

Consequence: Montrer que si p est un nombre premier et a un entier naturel quelconque alors a^p -a divisible par p ( c'est à dire a^p≡a [p] )

JUSQUE LA J'AI REUSSI!

Quelques applications:
a) Montrer que pour tout entier naturel a, a^13 -a est divisible par 26.
b) -Décomposer 561 en produit de facteurs premiers.
-Montrer que a^561 - a est un multiple de 3 , de 11 , de 17.
-En déduire que a^561≡ a [561]
-Que vous inspire ce résultat?

Donc pour la 3 ) je bloque car je sais que grace au théoreme vu plus haut a^13≡a [13]
mais comment on fait pour avoir 26 ??

et pour la b) je bloque aussi donc pour le premier tiret c'est bon quand même ^^
mais apres comment je montre que c'est des multiples de 3 , 11 et 17 ??

merci beaucoup j'ai une partie B) apres mais je la posterai quand j'aurai fini la parti A)

Bonjour Terra, c'est Joie de vivre qui t'encourage de continuer car tu es sur la bonne voie pour la question 3)a) :

a^13≡a [13]
donc a^13-a est divisible par 13
Comme 2 est premier avec 13 et 2 x 13 = 26, il reste à montrer que a^13-a est divisible par 2.
Cela se fait facilement en distinguant les 2 cas où "a est pair" et "a est impair".
Dans les deux cas, tu montreras facilement que a^13-a est pair !

Bon courage à toi
Joie de vivre
www.methode-ravoson.com

Bonjour,
Tu as dû démontrer dans la partie A que p étant premier et a non multiple de p, $a^{p-1}$ ≡1 modulo p
De plus , tu remarques que 2 ( = 3-1) divise 560 ( = 561-1).
Tu dois pouvoir te débrouiller avec ça.

Bonjour Joie-de-vivre tout d'abord merci beaucoup pour votre réponse! Je vais reprendre mon courage à deux mains pour essayer de terminer cet exercice!

Ba en faite j'ai essayé quelque chose mais je sais pas si c'est bon ou pas

si a est pair, toutes ses puissances sont pairs aussi et donc a^13-a est la différence de 2 nombre pair ce qui est donc un pair.

de même si a est un impair, toutes ses puissances sont impairs et a^13-a est la différence de deux impairs ce qui donne un pair.

dans tous les cas a^13-a est divisible par 2 car c'est un pair! on sait deja que c'est divisible par 13 (avec le théoreme) donc c'est aussi divisible par 26

je sais pas si c'est bon...

mathtous
Bonjour,
Tu as dû démontrer dans la partie A que p étant premier et a non multiple de p, $a^{p-1}$ ≡1 modulo p
De plus , tu remarques que 2 ( = 3-1) divise 560 ( = 561-1).
Tu dois pouvoir te débrouiller avec ça.

Je parlais de la question 3)b)

oui je parlais pour Joie-de vivre , je n'avais pas encore vu votre poste je suis vraiment désolée :-$

pour la question 3)b) j'ai donc fait ça: 561 = 3x11x17 et 3, 11 et 17 sont premiers
je pose N= a^561 -a = a(a^560 -1)

pour 3 donc
si a est divisilbe par 3, N aussi
sinon on utilise le théoreme avec p = 3
donc a^560 -1 = (a^280)^2 -1

donc (a^280)^2≡ 1 [3]

on multiplie par a et on a a^561≡ a [3]

et donc on a a^561 -a≡ 0 [3]

et j'ai utilisé le même principe pour 11 et 17

et en quoi on en déduit que a^561 a [561] a partir de ça? car ça on le sait directement avec le théoreme depuis le debut en fait...
ce que ça nous inspire ce serait donc la 2ème parti du théoreme je comprends pas bien où ils veuelent en venir là...

Citation
on multiplie par a et on a a^561≡ a [3]Attention : tout ce qui précède est vrai si a n'est pas multiple de p (3, 11 ou 17 ici ).
Mais l'égalité est évidente si a multiple de p.
Donc vraie pour tout a.

Citation
et en quoi on en déduit que a^561 a [561] a partir de ça? car ça on le sait directement avec le théoreme depuis le debut en fait...Non, non! car 561 n'est pas premier.
Mais ici, il suffit de remarquer que 3 , 11 et 17 sont premiers entre eux deux à deux.
Donc si a^561 -a est un multiple de chacun, il est multiple de leur produit.

oui et on en deduit que la reciproque est donc fausse car 561 est pas premier!

Citation
Attention : tout ce qui précède est vrai si a n'est pas multiple de p (3, 11 ou 17 ici ).
Mais l'égalité est évidente si a multiple de p.
Donc vraie pour tout a.

mais du coup c'est bon quand même ou... :s

ah oui en effet! j'avais même pas fait attention au fait qu'il fallait que p soit premier...

ceci était pour la parti A... il y a donc une parti B qui me parait encore plus dure que la partie A!!

B) une méthode de cryptage : le système RSA

Crée en 1978 aux Etats-Unis par Ronald Rivest, Adi Shamir et Léonard Adleman.
Soient p et q deux entiers naturels premiers, n=pq et e est un entier naturel n'ayant , en dehors de 1, aucun diviseur commun avec le produit (p-1)(q-1).
On choisit ici p=3, q=11 et e = 7

a) Vérifier que si d = 3, alors (p-1) (q-1) divise ed-1
b) Comment choisir l'entier naturel x, x<n , pour que $x^{ed-1}$ -1 soit un multiple de n?
c) Prouver que pour tout entier naturel x, x<n, $x^{ed}$ -x est un multiple de n.

je vais deja mettre ça pour la suite on verra apres ... on va essayer de pas se décourager... l'arithmétique c'est pas mon truc...

pour la a j'ai remplacé p , q et e , d par leur valeur on trouve
(p-1)(q-1) = 20 et ed-1 = 20 donc 20 divise 20
ça suffit pour ça
et apres je bloque pour la b) je suis encore en traind e chercher je suppose qu'il faut utiliser le théoreme au dessus...

Re bonjour,
Partie A :
561 met en effet en défaut la réciproque du petit théorème de Fermat.
Des nombres tels que 561 sont des nombres de Carmichael.

Partie B :
Applique le théorème de Fermat pour p puis pour q : il y a en effet une condition sur x.

on a $x^{p-1}$ ≡1 [p]
donc $x^{(p-1)(q-1)}$ ≡ 1 [p]
de la même façon on a $x^{q-1}$ ≡ 1 [q]
donc $x^{(q-1)(p-1)}$ ≡1 [q]

et donc on a $x^{(p-1)(q-1)}$ ≡1 [n]... et avec d = 3 on a (p-1)(q-1) = ed-1

pour la c y'a juste a multiplier par x de chaque côté mais pour la b) ce que j'ai fait ça montre pas vraiment comment il faut choisir x...

Pour la b) :
Citation
on a xp-1≡1 [p]A conditionque x ne soit pas multiple de p.
Même chose avec q.
Ici, avec l'exemple numérique choisi, ed-1 = (p-1)(q-1), mais plus généralement, il suffit que (p-1)(q-1) soit un diviseur de ed-1 ( c'est d'ailleurs le libellé de la question 1)a).

Ensuite, il suffit de multiplier par x
maisc'est dans le cas où x n'est pas multiple de p.
Sinon, si x est multiple de p, x ≡ 0[p] donc x^(ed) ≡0[p] ≡ x[p] puisque x≡0.
Et x^(ed) ≡x [q] ( si x n'est pas un multiple de q )
Donc, p et q étant premiers entre eux, x^(ed)≡x [n=pq]

Même raisonnement si x est multiple de q.

a oui y'a la condition du théoreme "a un naturel non divisible par p..."

donc en faite pour choisir x il faut que x ne soit pas divisible par pq?

mais dans ce cas c'est bon pour tout x entier naturel inférieur à n parce que si x est inférieur a n il n'est pas divisible par n donc pas divisible par pq...

heu je sais pas si tout ce que je dis c'est juste là...

Si x n'est divisible ni par p, ni par q, tu peux raisonner comme tu l'as fait : appliquer le théorème pour p , conséquences, puis pour q, conséquences.
Il suffit ensuite de multiplier par x pour avoir l'égalité du c.

Si x est multiple de p mais pas de q , j'ai détaillé.
Même chose si x est multiple de q mais pas de p.
Si x est multiple de p et de q ( donc de pq) :
x multiple de p donc comme je l'ai fait : x^(ed) ≡0[p] ≡ x[p]
Si x est aussi multiple de q : même raisonnement : x^(ed) ≡0[q] ≡ x[q]
Et il n'y a plus qu'à conclure.
L'important est d'aboutir dans chaque cas ( il y en a donc 4 en tout ) à :
x^(ed)≡ x[p] et x^(ed)≡ x[q] .
Que ce soit en utilisant ou non ( selon les cas ) le théorème de Fermat.
La conclusion est ensuite la même, p et q étant premiers entre eux, x^(ed)-x est multiple à la fois de p et de q donc de leur produit.

Attention à ta dernière remarque : si x est inférieur à n, il n'est pas divisible par pq ( à moins d'être nul ...) , mais il peut quand même être divisible par p ou par q.

sauf que on cherche pas $x^{ed-1}$ -x multiple de n...

on cherche soit $x^{ed-1}$ -1 multpiple de n ou $x^{ed}$ -x multiple de n...

oula je comprends plus rien là...

Oui, c'est ma faute : désolé je n'ai pas fait attention.
Je viens de modifier mes deux derniers messages.
Dis-moi si cela convient .

Si x non multiple de p , x^(ed-1) ≡1 [p]
Donc x^(ed) ≡x[p]
Même chose pour q.

Si x est multiple de p , on a directement x^(ed) ≡ x [p]
Même chose pour q.

y'a encore un ed-1 en trop non dans le premier message modifié non? ^^

oui sinon j'ai bien compris on montre bien tous les cas là.
donc on voit que pour la question b) il faut que x soit ni multiple de p ni multiple de q pour que $x^{ed-1}$ -1 soit multiple de n

et on voit bien que pour la c) c'est bien pour tout entier naturel

voila si ce que je dis est vrai je pense avoir comprit pour cette partie

on voit pouvoir faire la suite xD ah j'en finirai jamais lol

Citation
Ici, avec l'exemple numérique choisi, ed-1 = (p-1)(q-1), mais plus généralement, il suffit que (p-1)(q-1) soit un diviseur de ed-1 ( c'est d'ailleurs le libellé de la question 1)a).
Ici ?
Non : il s'agit bien de ed-1

ah non pas ici je voulais parler de ce ed-1 :

Citation
Sinon, si x est multiple de p, x ≡ 0[p] donc x^(ed) ≡0[p] ≡ x[p] puisque x≡0.
Et x^(ed-1) ≡x [q] ( si x n'est pas un multiple de q )

OK : c'est bien ed et pas ed-1 : j'ai modifié.
Quand il y a " ≡ 1" c'est ed-1
Quand il y a " ≡ x" c'est ed

exact on aurait du dire ça depuis le début ^^ désolée ça m'embrouillait un peu

donc avec les 4 cas on voit bien que pour tout entier naturel x, x<n $x^{ed}$ -x est multiple de n! j'ai bien comprit comme ça merci!

voici la suite!

Soit x un entier naturel non nul, avec x<n.

a) Quel est le reste de la division de $x^{ed}$ par n
b) Soit c le reste de la division de $x^e$ par n.
Démontrer que le reste de le division de $c^d$ par n est x.

pour la a avec ce qu'on a fait plus haut ça parait facile
on a vu que $x^{ed}$ -x est un multiple de n

donc $x^{ed}$ -x≡ 0 [n]

et donc $x^{ed}$ ≡x [n] donc le reste est x

pour la b) je cherche encore

Citation
2) Soit x un entier naturel non nul, avec xAvec x < n?
Si oui, ta réponse a) me paraît correcte.

oui dsl avec x< n... je cherche la suite si jamais je bloque je reviendrai...

Facile :
Soit c le reste de la division de $x^e$ par n : ça signifie que
$x^e$ ≡ c [n] ( c < n)

oui ça j'avais comrpis quand même
c'est pour la demonstration d'apres que je cherche ^^

donc je pense a ceci pour la b)

on a $x^e$ ≡c [n] (c<n)
on peut mettre la puissance de chaque côté: $x^{ed}$ ≡ $c^d$ [n]
et on sait grace a la question 2)a) que $x^{ed}$ ≡x[n]

donc on a $x^{ed}$ ≡ $c^d$ ≡x[n]

donc le reste de la division de $c^d$ par n est x

je pense que pour ça j'ai bon aussi

voici enfin la dernière partie de l'exercice!!

On admettra que les propriétés démontrées aux questions précédentes pour des valeurs particulières de p, q et e sont valables en toute généralité, autrement dit que:

pour tous nombres premiers p et q, et pour tout entier naturel e sans diviseur commun avec (p-1)(q-1), il est possible de trouver un entier naturel d tel que (p-1)(q-1) divise ed-1 (pour le démontrer, on utilise le théorème de Bézout)
x étant un entier naturel non nul inférieur à n, si c est le reste de la division de $x^e$ par n, alors le reste de la division de $c^d$ par n est x.

Représentons les lettres successives de l'alphabet par les nombres 01,02,...26, le "!" par 27, le "." par 28 et l'espace blanc par 29. Chaque lettre (ou signe) x ainsi représentée vérifie x<n. On convient de crypter le caractère x en le remplaçant par le reste c de la division de $x^e$ par n.

a) Crypter le mot FERMAT, représenté par le mot x1x2x3x4x5x6 = 060518130120

b) soit c1c2c3c4c5c6 le mot crypté ainsi obtenu. Pour chaque i {1,2...,6], calculer le reste de la division de $(c$ _i $^d$ par n. Vérifier que l'on obtient le mot 060518130120 ( c'est à dire FERMAT) comme cela est démontré en B.4.

c) Décrypter le mot 290601222703.

je suis en train de chercher cette dernière partie!

Terra

Bonjour Joie-de-vivre tout d'abord merci beaucoup pour votre réponse! Je vais reprendre mon courage à deux mains pour essayer de terminer cet exercice!

Ba en faite j'ai essayé quelque chose mais je sais pas si c'est bon ou pas

si a est pair, toutes ses puissances sont pairs aussi et donc a^13-a est la différence de 2 nombre pair ce qui est donc un pair.

de même si a est un impair, toutes ses puissances sont impairs et a^13-a est la différence de deux impairs ce qui donne un pair.

dans tous les cas a^13-a est divisible par 2 car c'est un pair! on sait deja que c'est divisible par 13 (avec le théoreme) donc c'est aussi divisible par 26

je sais pas si c'est bon...

Salut Terra, c'est Joie-de-vivre qui constate que tu as pu bien avancer avec Mathous, c'est super ! Pour ma part, c'est correct ta réponse !!!
Désolé de t'avoir répondu un peu tard car, en ce moment, je n'ai pas la possibilité de me connecter souvent !

Très bonne continuation à toi !
A la prochaine sur Mathforu
Joie-de-vivre

Re bonjour.
C'est toujours pour p=3 , q=11, e=7 ?
( d'où n=33 et d = 3)

Il n'y a qu'à faire les calculs modulo 33.
Tu peux utiliser ma calculatrice disponible sur ce lien ( si Neuf/SFR veut bien fonctionner ... ) :

Calculatrice arithmétique

Bonjour!

Tout d'abord merci Joie-de-vivre pour votre réponse ^^ oui en effet j'ai pu bien avancer! je pense même avoir fini!

Donc j'avais envoyé la fin mais je l'ai fait hier soir donc voici ce que j'ai fait!

par exemple pour la première lettre c'est 06, donc j'ai apres on a $6^7$ ≡30[33]

et j'ai fait ça avec toutes les lettres!

et donc au final le mot crypté donne:
30 14 06 07 01 26!

pour la b) par exemple la première lettre crypté que j'ai trouvé c'était 30
et $30^3$ ≡6 [33] donc on retrouve bien la x de départ 06 qui est la lettre F!
j'ai fait ça pour toutes les lettres et je retrouve le mot fermat!

enfin pour la c) par exemple la première lettre crypté est 29
et on sait que $29^3$ ≡x [n =33]
et donc $29^3$ ≡2 [33]
et 02 est la lettre B!

j'ai fait la même méthode pour toutes les lettre et je trouve:

BRAVO!

voila je pense que c'est bon comme ça... je sais pas si pour la rédaction ça suffit... mais comme c'est toujours le même cas avec e et d donné je pense que c'est bon...

De rien.