exercice congruence

[invite93845cf6]

Bonjour à tous, j'ai un exercice type bac à faire pour demain et dans la question 3 de cet exercice, il m'est demandé :

Soit a un entier naturel non divisible par 7. Montrer que est congru à 1 modulo 7.
-----

[invite93845cf6]

Je ne sais pas quel raisonnement utiliser: récurrence ou disjonction de cas ? Pour la récurrence, je n'arrive pas à me ramener à quelque chose de la forme 7k+1 dans la prtie hérédité.

[Gwyddon]

Bonjour,

La récurrence ne sert à rien, par contre la disjonction de cas peut être intéressante, quoique fastidieuse...

Tu dois étudier les 6 cas possibles : a congru à 1, a congru à 2, a congru à 3, a congru à 4, a congru à 5 et a congru à 6.


Il y a néanmoins beaucoup plus rapide (en fait immédiat), si tu utilises un théorème bien particulier. Ceci dit, peut-être ne l'as-tu pas encore vu en cours...

[invite652ff6ae]

Il y a néanmoins beaucoup plus rapide (en fait immédiat), si tu utilises un théorème bien particulier. Ceci dit, peut-être ne l'as-tu pas encore vu en cours...

Et quel est ce théorème ?

Merci

 Cliquez pour afficher

Edit : le petit théorème de Fermat Mais on ne le voit pas en cours effectivement...

[A voir en vidéo sur Futura]

[Gwyddon]

Et quel est ce théorème ?

Merci

Je ne vais pas te le dire, ce serait équivalent à donner la solution directement

Je t'invite à relire ton cours, et voir si parmi les théorèmes que tu as étudié l'un d'eux ne te serait pas utile. Mais encore une fois, il est peut-être trop tôt dans l'année pour que tu aies vu ce théorème, auquel cas la disjonction des cas reste une solution valable

[invite93845cf6]

Le problème est que je ne sais pas comment montrer que a^6 peut-être congru à 1 modulo 7. J'ai essayé de montré que a^6 - 1 est multiple de 7 mais je n'y suis pas arrivé.
Sinon quel ce théorème ?
Merci.

[Gwyddon]

Tu as essayé la disjonction de cas ?

Sinon pas la peine d'insister, je ne vais pas non plus faire l'exercice à ta place. Relis ton cours, si tu as vu le théorème dont je te parles, tu le trouveras, et sinon tant pis tu le verras plus tard dans l'année

A la rigueur, une fois résolu l'exercice je t'indiquerai le théorème.

[invite93845cf6]

Ah non, je n'ai pas vu le théorème de Fermat.
Si je veux faire par disjonction de cas, dois-je remplacer a par 7k+1, 7k+2, 7k+3, 7k+3 , 7k+4, 7k+5, 7k+6 ? Parce que pour 7k+1 je trouve quelque chose du type 7k+1 et de manière analogue pour les autres cas. Je suis un peu perdu là.

[Gwyddon]

Je sens que tu as du mal avec les congruences

Alors petit rappel :

si a congru à b modulo n
a' congru à b' modulo n

alors a*a' congru à b*b' modulo n

(si tu n'es pas convaincu, essaye de le démontrer).


Sinon bien trouvé, c'est effectivement le (petit) théorème de Fermat. Mais bon si tu ne l'as pas vu, tu oublies

[invite652ff6ae]

Alors petit rappel :

si a congru à b modulo n
a' congru à b' modulo n

alors a*a' congru à b*b' modulo n

Mais ici la propriété à utiliser c'est plutôt que : si x congru à y (mod p) alors x^n congru à y^n (mod p) non ?

[invite93845cf6]

Je sens que tu as du mal avec les congruences

Alors petit rappel :

si a congru à b modulo n
a' congru à b' modulo n

alors a*a' congru à b*b' modulo n

(si tu n'es pas convaincu, essaye de le démontrer).


Sinon bien trouvé, c'est effectivement le (petit) théorème de Fermat. Mais bon si tu ne l'as pas vu, tu oublies

J'ai déjà démontré cette propriété étant donné qu'elle était demandé dans la question précédente. Le problème est en fait que je ne sais pas si a est congru à 1 ou pas modulo 7. C'est ça qui me fait bloquer.

[invite93845cf6]

Est-ce que c'est bon si je dit ça:
Il existe forcément un entier naturel a tel que a congru à 1 (7).
Donc, selon les règles opératoires utilisables pour les congruences qui sont les multiplications et opérations de puissances on a :
a^6 congru à 1^6 (7) ce qui revient à écrire a^6 congru a1 (7)
car 1^6 = 1.

[Gwyddon]

C'est bien, tu as fait 1 cas dans la disjonction de cas

Il reste à faire les 5 autres : a congru à 2, 3, 4, 5, 6 modulo 7...

[invite93845cf6]

C'est bien, tu as fait 1 cas dans la disjonction de cas

Il reste à faire les 5 autres : a congru à 2, 3, 4, 5, 6 modulo 7...

Ok, merci beaucoup !