Besoin de solutions avec étape svp

Besoin de solutions avec étape svp
Message de snop92 posté le 21-03-2020 à 12:26:21 (S | E | F)
Le reste de la division euclidienne de 74^547 par 12 ( avec le modulo et congruence ) avec étape svp Merci de votr aide ))

---

Réponse : Besoin de solutions avec étape svp de tiruxa, postée le 21-03-2020 à 14:34:08 (S | E)
Bonjour

Première étape

Chercher le reste de la division de 74 par 12 :

74=6*12+2

Cela signifie 74 congru à 2 modulo 12.

Deuxième étape

Utiliser la propriété concernant la puissance et la congruence.
Trouver ainsi à quel nombre est congru 74², 74^3, 74^4 etc...
En déduire une remarque que l'on généralisera et démontrera pour 74^n, par exemple par récurrence.

Conclure alors pour n=547.

---

Réponse : Besoin de solutions avec étape svp de lemagemasque, postée le 21-03-2020 à 16:08:46 (S | E)
Bonjour,

Je complète le message de tiruxa.

Avant-propos : comme il est difficile d'écrire directement en LaTeX sur le site, je noterai = au lieu du symbole usuel des congruences (triple égal).

- 1re étape :
On remarque que 74 >= 12 (le modulo), donc au lieu de travailler avec des grands nombres, on peut tâcher de le diminuer.
On le remplace alors souvent par le reste de la division euclidienne de 74 par 12 (sauf si on peut avoir 74 = -1 (mod quelque chose), ce qui est très pratique pour les puissances), car c'est le plus petit nombre positif possible congru à 74.
Pour trouver ce reste, différents moyens :
- n'utiliser que les propriétés sur les congruences, et retrancher autant de fois 12 à 74, jusqu'à tomber sur un nombre compris entre 0 et (12 - 1) :
74 = 62 = 50 = 38 = 26 = 14 = 2 (mod 12)
- diminuer le nombre de soustractions, en retranchant des multiples de 12
74 = 74 - 48 = 26 = 26 - 24 = 2 (mod 12)
- effectuer la division euclidienne de 74 par 12 (peut être parfois un peu long pour des grands nombres, mais ici, ça marche tout aussi bien)

- 2e étape (je cite tiruxa, en modifiant légèrement)
Trouver à quel nombre est congru 2², 2^3, 2^4, etc.
En déduire une remarque que l'on généralisera et démontrera pour 2^n, par exemple par récurrence (ou réécrire la puissance comme 547 = 2 * 273 + 1 (par exemple) et par conséquent 2^547 = (2^2)^273 * 2, mais peu efficace ici. Ça marche mieux quand on peut écrire 547 = p * q + r avec p^q = +/- 1 (mod 12))

Bon courage !

Pour rappel :
Étant donné 2 entiers positifs a, n (avec n différent de 0)
Si a = a' (mod n) alors a = a' - k*n (mod n) avec k pris dans Z
et, pour tout entier p, a^p = a'^p (mod n)

---

[POSTER UNE NOUVELLE REPONSE] [Suivre ce sujet]

Cours gratuits > Forum > Forum maths