Arithmètique Modulaire - Forum Mathématiques du collège et du lycée

Haexyrus · 27/12/2007, 16h29

Bonjour,

Um... voilà : Je suis en 1ère S, et je n'ai aucune idée sur l'arithmètique modulaire ni la congruence (enfin, si, mais seulement pour les angles orientés) mais j'ai un problème qui nécéssite l'utilisation de certains outils appartenant à cette catégorie. Ce problème ne m'a pas été donné en cours, mais c'est juste que j'aime découvrir des choses par moi même et la je trouve une difficulté.

En gros, ça consiste à trouver le reste d'une division euclidienne de la forme n^k / p avec n et k des entiers (k étant très grand) et p un nombre premier tq n et p premiers entre eux.

J'ai fouillé un peu sur les archives ici et je suis tombé sur ça:

http://forums.futura-sciences.com/ar...clidienne.html

J'ai appliqué la première méthode pour deux cas, et ça marche bien même si c'est un peu long, mais je trouve un problème dès que n > p : comment écrire un multiple de p à l'aide de puissance de n alors que n > p ?

Je suis passé à chercher la deuxième méthode indiquée par Mr mmy : le petit thèorème de Fermat (c'est bien celui ci qu'il faut, non ?) mais je n'arrive pas à faire le lien entre le problème et le thèorème et je viens ici dans l'espoir que quelqu'un m'éclaire.

Si vous préférez le faire avec des nombres précis, je propose 54^139 / 7, même si je préfére que ça soit fait en général pour éviter de confondre en appliquant.

Merci d'avance

**MiMoiMolette** · 27/12/2007, 16h52

Salut,

Si tu veux utiliser le concept des congruences, "quel est le reste dans la division euclidienne de a par b" revient à chercher c tel que $a \equiv b [c]$ (a est congru à b modulo c)

Le théorème de Fermat est très pratique :

Si a et p premiers entre eux (avec p premier - c'est-à-dire que a n'est pas multiple de p), alors on peut écrire que :

$a^{p-1} \equiv 1 [p]$

Enfin c'est Euler ou Fermat ça... Ce n'est pas si important, l'un étant corrélé à l'autre

Bref, tout ce blabla pour quoi ?

Tu as a = 54
p = 7
a et p premiers entre eux, no souci.

Ensuite, tu dois calculer 54^139 ? Nooon, en bon mathématicien, on est flemmard

Propriété :
Si $a \equiv b [n]$ alors $a^c \equiv b^c [n]$
En quoi cette propriété est intéressante ?
Si tu trouves a congru à 1 modulo n, alors c'est tout bon !

Et c'est là qu'Euler (ou Fermat) intervient : tu sais que 54^6 est congru à 1 modulo 7.

L'astuce est d'écrire la division euclidienne de 139 par 6.
Tu auras 139 = 6q+r.

Or, $a^{bc} = (a^b)^c$

Donc si a^b congru à 1 modulo 7, alors a^(bc) est cngru à 1 modulo 7 aussi

Bref...Désolée, j'ai un peu tout balancé, en mélangeant certains noms de variables.... J'espère que c'est quand même un peu clair ^^

**MiMoiMolette** · 27/12/2007, 17h02

Pour résumer :

Si tu cherches le reste dans la division euclidienne de a^b par n :

- Cherche c tel que a^c soit congru à 1 modulo n (reste dans la division euclidienne de a^c par n = 1).
Ce point peut être simplifié si n est premier -> Application du théorème d'Euler (now j'en suis quasiment sûre : Le théorème d'Euler, qui découle du théorème de Fermat me semble plus simple d'application ^^) :
$a^{p-1} \equiv 1 [p]$

- Ecris la division euclidienne de b par c : b = cq+r.

- $a^b = a^{cq+r} = (a^c)^q*a^r$
Or, $a^c \equiv 1 [n]$
Et comme on a la propriété : si $x \equiv y [n]$ alors $x^t \equiv y^t [n]$ (1) ou $t*x \equiv t*y [n]$ (2)

Donc $(a^c)^q \equiv 1^q [n]$ d'après (1)
$(a^c)^q \equiv 1 [n]$

Et donc $a^b = (a^c)^q * a^r \equiv a^r [n]$ d'après (2)

Voili voilou, j'espère que ce sera plus clair :/

Haexyrus · 27/12/2007, 20h03

Voyons voir ...

Pour l'exemple que j'ai proposé, je devrais trouver 5 comme reste, non ?

Si c'est le cas, je me dois de vous remercier et j'irai directement appliquer sur d'autres exemples plus compliqués

**MiMoiMolette** · 27/12/2007, 20h35

J'ai trouvé 5 aussi ^^

Mais attention, tu n'as pu utiliser le théorème d'Euler que parce que 54 et 7 étaient premiers entre eux.

Autrement, tu aurais pu faire : 54 congru à 5 modulo 7. 54^2 congru à 5^2 = 25 modulo 7, i.e. 4 modulo 7, et ainsi de suite, jusqu'à trouver 1 =)

C'est bien si tu l'as compris !

Haexyrus · 27/12/2007, 21h35

Je crois que j'ai bien assimilé le mechanisme, merci bien

Il ne me reste qu'à faire quelques applications de plus pour bien graver le truc dans ma mèmoire, et voilà que j'ai une partie d'avance sur le programme de l'année prochaine (Terminale S)

Merci encore, et à une prochaine j'espère

**MiMoiMolette** · 27/12/2007, 21h37

Woh woh woh

Ce n'est qu'une infiiiiime partie ça ^^ bien que ce soit une méthode utile à retenir et assimiler.

Si tu veux continuer sur la spé maths (arithmétique), ce fil pourra te donner, en plus de fil à retordre, quelques exercices d'application et l'innovation de notions pour toi ! : http://forums.futura-sciences.com/thread174211.html

Et si tu as des questions, eh bien ma foi... tu sais où aller

^^

Bon courage pour la suite,

(et de rien)