Arithmetique

[Huntere]

Bonsoir , je bloque à une question de mon dm de spécialité , c 'est la question 1 si quelqu’un peut m'aider



Partie A
1) Soit x ∈ N et n un entier naturel tel que n ≡ 1 mod 28.
En utilisant le théorème de Fermat, prouver que x^n ≡ x [ ] 29.

2/ On considéré l'équation (E) : 17x − 28y = 1 o`u (x, y) ∈ Z

a) Quel théorème permet d’affirmer que l'équation (E) admet au moins un couple solution d'entiers relatifs ?

b) En utilisant l'algorithme d'Euclide, trouver un tel couple solution.


1) blocage

petit théorème de Fermat x^(n-1) ≡ 1 (28)
donc x^n ≡ x (28) en multipliant par x de chaque coté.
je ne sais comment passer à x^n ≡ x (29)

2/

a) théorème de Bézout

b) je trouve x=5 y=-3
-----

[Elwyr]

Bonjour,

Je ne suis pas très au point sur le petit théorème de Fermat, mais il me semble que vous ne pouvez pas l'appliquer aussi brutalement... L'énoncé (présent sur wikipédia) est : si p est un nombre premier et si a est un entier non multiple de p, alors a^p-1 = 1 [p] (j'écris une égalité au lieu d'un modulo, j'espère que vous ne m'en voudrez pas).

Le cas où x est un multiple de 29 se traite assez bien (mais il faut le faire !) donc dans la suite je vais supposer que ce n'est pas le cas.

Vous cherchez à établir des congruences modulo 29 (qui lui est premier). C'est donc sans doute à lui que vous allez appliquer le théorème de fermat.
Qu'obtenez-vous si vous l'appliquez comme ça ? Pouvez-vous relier la relation que vous obtenez à (n-1) ?

Par ailleurs, votre dernier résultat est faux (pour une raison de signes : vous sommez deux termes qui seront visiblement positifs, et pas qu'un peu. Vous vouliez peut être dire y = 3, ou alors vous avez mal recopié votre équation).

[S321]

petit théorème de Fermat x^(n-1) ≡ 1 (28)
donc x^n ≡ x (28) en multipliant par x de chaque coté.
je ne sais comment passer à x^n ≡ x (29)

28 n'est pas un nombre premier, impossible d'appliquer le petit théorème de Fermat modulo 28.

Par contre 29 lui est bien premier... Essayez de réunir les hypothèses du théorème avant de l'appliquer.

[Huntere]

Par ailleurs, votre dernier résultat est faux (pour une raison de signes : vous sommez deux termes qui seront visiblement positifs, et pas qu'un peu. Vous vouliez peut être dire y = 3, ou alors vous avez mal recopié votre équation).

Oui , c’était bien y = 3


pour en revenir à la question ;

une corolaire du petit théorème de Fermat montre que Si A entier et que p est premier alors (A^p) - A est divisible par P

donc ici

comme 29 est premier et x appartenant au entier |N alors selon une corolaire du petit théorème de Fermat , x^29 ≡ x (29)

je vois pas comment utiliser n≡ 1 (28)
n-1≡0 (28)
(n-1)=28k
28 ≡ 28 (29) <=> 28k≡28k (29) <=> (n-1)≡28k (29)...

[A voir en vidéo sur Futura]

[Huntere]

Ah !!

n≡1 (28) <=> n-1≡0 (28) or pgcd(28 ; 29) 1 donc x^(n-1) ≡ 1 (29 ) (n-1) ^29 = 1

<=> x^(n) ≡ x (29) en multipliant par x de chaque cotés

mais faut-il distinguer deux cas ? x divisible par 29 et x non divisible par 29 ( application du petit théorème de Fermat )

[Elwyr]

Pour appliquer le théorème de fermat proprement, il faut en effet distinguer les deux cas.

Je ne suis pas sûr de comprendre le rapport entre le pgcd de 28 et 29 et ce que vous en déduisez... Ni à quel moment vous prouvez que x^n-1 = 1 [29] (dans le cas où x n'est pas un multiple de 29).

[Huntere]

j'ai fait une erreur je n'ai pas pris en compte le K (n-1)=28k j'ai supposé pgcd(28k;29)=1 ..... absurde...

cas 1 = x non multiple par 29

29 premier et pgcd (x; 29)= 1
donc on peut écrire avec le petit théorème de Fermat que x^28 ≡ 1 (29) et donc x^29 ≡ x (29)
mais je n'ais pas prouver x^n ≡ x (29)

Cas 2 : x multiple de 29

x ≡ 0 (29)

x^n ≡ 0 (29) ?

[Elwyr]

Personnellement, quand je bloque dans une démonstration, il m'arrive souvent de me dire "oh, ce serait bien si...", comme dans "oh, ce serait bien si cette fonction était monotone...". Ca me donne une idée de ce que je peux avoir envie de montrer.

Ici, j'aurais envie de dire "oh, ce serait bien si à la place de ce 28, j'avais n-1..."
Pouvez-vous exprimer n-1 en fonction de 28 ? Cela vous permet-il d'avancer (voire de conclure) ?

Pour ce qui est de votre deuxième cas, Si x = 0 [29] et x^n = 0 [29], finalement x^n = x[29] (n'oubliez pas de mentionner la conclusion attendue).

[Huntere]

n-1≡0 (28)

On a le droit de remplacer des puissance dans des congruences ? si oui on a :

x^28≡ 1 (29) ôr n-1 ≡ 0 (28) donc
x^(n-1) ≡ 1 (29) en multipliant par x de chaque coté on a :
x^n ≡ x (29) pour x non multiple de 29

si x multiple de 29 alors x=29k ≡ 0 (29)
x^n≡0 (29)

conclusion x^n≡ x (29) n'est vrai que si 29 ne divise pas x

[Elwyr]

Je ne sais pas ce que vous voulez direz par "remplacer des puissances dans des congruences". Ce que je sais, c'est que si a = b [p] alors a ⁿ = b^ⁿ [p]

Concrètement, ça veut dire quoi, que n-1 = 0 [28] ? La réponse à cette question doit vous permettre de conclure.

Ensuite, je ne suis pas d'accord avec votre conclusion dans le deuxième cas. Votre cours dit que si a = b[p] et b = c [p], alors a = c [p]... Vous devez pouvoir l'appliquer ici pour arriver à la conclusion juste.

[Huntere]

Concrètement, ça veut dire quoi, que n-1 = 0 [28] ? La réponse à cette question doit vous permettre de conclure.

je ne comprend pas trop , sa veut que n-1 est divisible par 28 et que la division euclidienne de n par 28 a pour reste 1 ( donc pgcd(n;28)=1 ) , je mélange un peu tout je pense ....

si a = b [p] alors a n = b^n [p]

la réciproque est vrai ?

x^28 ≡ 1 (29) => x ≡ 1 (29) ? et donc x^(n-1) ≡ 1 (29)


mais de même je comprend pas le passage de x^28 à x^n-1

si a = b[p] et b = c [p], alors a = c [p]

Pour le 2eme cas :

la transitivité fait que comme x ≡ 0 (29) et x^n ≡ 0 (29)
x^n ≡ x ≡ 0 (29)

x^n ≡ x (29) .

[Elwyr]

Heu... Ca ne m'étonnerait pas que la réciproque soit vraie pour les puissances impaires, mais pas pour les puissances paires : 4 = 1 [3] mais 2 = -1 [3] (ça vient du fait que connaître le carré d'un nombre ne permet pas d'en déduire son signe, sûrement).

Mais de toute façon, ce n'est pas nécessaire ici. n-1 est divisible par 28, ou bien c'en est un multiple... Il existe donc un entier k tel que n - 1 = 28k (k n'est autre que le quotient de n par 28, ce qui prouve que donner des noms aux objets qu'on manipule, c'est très très pratique).

[Huntere]

Il existe donc un entier k tel que n - 1 = 28k (k n'est autre que le quotient de n par 28, ce qui prouve que donner des noms aux objets qu'on manipule, c'est très très pratique).

x^28k ≡ 1^k (29) <=> x^(n-1) ≡ 1(29) c'est la ou vous voulez en venir ?
|
|-->(x^28)^k ≡ 1^k (29)

[Elwyr]

Exactement. Voilà l'exercice résolu !

[Huntere]

Un grand merci pour votre aide ( vous m'avez aussi instruit )

Bonne soirée /nuit