Nous avons simplifié la congruence en utilisant le fait que 9 ≡ 2[7]. Le but étant
d’obtenir à la fin une congruence avec un entier naturel inférieur ou égal à 6 il est
intéressant, à chaque étape, de simplifier au maximum la congruence.
En élevant encore deux fois au carré on obtient de même :
10 4 ≡ 4 [7]
10 8 ≡ 16 [7]
≡ 2 [7]
et enfin, en multipliant la relation avec 10 8 par celle avec 10 2 :
10 10 ≡ 4 [7]
Comme 0 4 7 − 1 ceci montre que le reste de la division euclidienne de 10 10
par 7 est 4.
Comme u 2 = u
10
1 , on a :
u 2 ≡ 4 10 [7] .
On peut reprendre un raisonnement analogue au précédent en partant de 4 au lieu
de 10 et on obtient, tous calculs faits :
4
10
≡ 4[7]
i.e. le reste de la division euclidienne de u 2 par 7 est 4.
On voit alors qu’en répétant l’opération (élévation à la puissance 10) on obtiendra
toujours 4 : voici notre réponse qu’il ne reste plus qu’à formaliser dans une hypothèse de récurrence.
Pour n ∈ N ∗ posons H n : « u n ≡ 4[7] ».
• H 1 : vraie, c’est le calcul fait précédemment en exemple.
• Hérédité : soit n ∈ N ∗ tel que H n soit vraie, i.e. :
u n ≡ 4[7].
Alors :
u n+1 ≡ 4
10 [7].
© Dunod. La photocopie non autorisée est un délit.
255
Chapitre 11 • Arithmétique
9782100547678-Fresl-C11.qxd 5/07/10 8:49 Page 255