Divisibilité dans $\mathbb{Z}$ et congruences

Divisibilité et récurrence - Exercice 3

6 min
15
Question 1

En utilisant un raisonnement par récurrence, démontrer que, pour tout entier naturel nn, 23n12^{3n}-1 est divisible par 77.

Correction
Pour tout entier naturel nn, posons la propriété Pn:P_{n} : « 23n12^{3n}-1 est divisible par 77 »
Etape d’initialisation :\red{\text{Etape d'initialisation :}}
23×01=201=11=02^{3\times0} -1=2^{0} -1=1-1=0
Or 00 est bien divisible par 77
La propriété P0P_{0} est vraie.
Etape d’heˊreˊditeˊ :\red{\text{Etape d'hérédité :}}
On suppose qu'il existe un entier kk tel que la propriété PkP_{k} soit vraie c'est-à-dire 23k12^{3k} -1 est divisible par 77 et vérifions si la propriété est également vraie au rang k+1k+1 .
La propriété au rang k+1{\color{blue}{k+1}} s'écriera : 23(k+1)12^{3\left({\color{blue}{k+1}}\right)} -1 autrement dit 23k+312^{3k+3}-1
Par hypothèse de récurrence :
23k12^{3k} -1 est divisible par 77 . Cela signifie qu'il existe un entier A\pink{A} tel que 23k1=7A2^{3k} -1 =7\pink{A}
Partons de l'expression de la propriété au rang k+1k+1, il vient que :
23k+31=23k×2312^{3k+3}-1=2^{3k}\times2^{3}-1
23k+31=23k×812^{3k+3}-1=2^{3k} \times {\color{orange}{8}}-1
23k+31=23k×(7+1)12^{3k+3}-1=2^{3k} \times \left({\color{orange}{7+1}}\right)-1
23k+31=23k×7+23k×112^{3k+3}-1=2^{3k} \times {\color{orange}{7}}+2^{3k} \times {\color{orange}{1}}-1
23k+31=23k×7+23k12^{3k+3}-1=2^{3k} \times 7+2^{3k} -1 . D'après l'hypothèse de récurrence, nous savons supposé vraie que 23k1=7A2^{3k} -1 =7\pink{A}.
Ainsi :
23k+31=23k×7+7A2^{3k+3}-1=2^{3k} \times 7+7\pink{A} . Nous pouvons factoriser par 77 l'expression . Ce qui nous donne :
23k+31=7(23k+A)2^{3k+3}-1=7\left(2^{3k} +\pink{A}\right)
Nous savons que kk est un entier et de ce fait l'expression 23k+A2^{3k} +\pink{A} est également un entier que l'on note par exemple B=23k+A{\color{brown}{B}}=2^{3k} +\pink{A}.
Soit : 23k+31=7×B2^{3k+3}-1=7\times{\color{brown}{B}}
Il en résulte donc que 23k+312^{3k+3}-1 est bien divisible par 77.
Ainsi la propriété Pk+1P_{k+1} est vraie.
Conclusion :\red{\text{Conclusion :}}
Puisque la propriété P0P_{0} est vraie et que nous avons prouvé l'hérédité, on peut en déduire, par le principe de récurrence que pour tout entier naturel nn, on a PnP_{n} vraie, c'est à dire que pour tout entier naturel nn, on a bien :
23n12^{3n}-1 divisible par 77 .