1. $123 = 3\times41$ donc les diviseurs de 123 sont: 1, 3, 41, 123.

2. $56=2^3\times 7$ donc les diviseurs de 56 sont:

   • les facteurs premiers et 1: 1, 2, 7;
   • les produits à deux facteurs premiers: $2\times2=4$, $2\times7 = 14$;
   • les produits à 3 facteurs premiers: $2^3=8$ et $2^2\times7=28$;
   • les produits à 4 facteurs premiers: $2^3\times7=56$.
   L'ensemble des diviseurs de 56 est donc : $\{1;2;4;7;8;14;28;56\}$.

3. $78=2\times3\times13$ donc les diviseurs de 78 sont:

   • les facteurs premiers et 1: 1, 2, 3, 13;
   • les produits à deux facteurs premiers: $2\times3=6$, $2\times13 = 26$ et $3\times13=39$;
   • les produits à 3 facteurs premiers: $2\times3\times13=78$.
   L'ensemble des diviseurs de 78 est donc : $\{1;2;3;6;13;26;39;78\}$.
4. $\numprint{1517}=37\times41$ donc les diviseurs de $\numprint{1517}$ sont 1, 37, 41 et $\numprint{1517}$.

Voici le programme complété:

def liste_diviseurs(n):
L = []
for k in range(1,abs(n)+1):
	if n%k == 0:
		L.append(k)

return L

Comme $n$ est un entier relatif, il ne faut pas oublier de faire appel à sa valeur absolue dans la boucle qui parcourt tous les entiers naturels de 1 à $n$.

Ainsi, dans ce programme, $k$ désigne un entier de $[1; n]$ (n'oublions pas qu'en Python, $\texttt{range(a,b)}$ désigne la liste des entiers de $a$ (compris) à $b-1$ (compris).

Dans la boucle, on teste si $n$ est divisible par $k$ (avec le test « $\texttt{if n\%k == 0}$ »); si tel est le cas, on ajoute à la liste $\texttt{L}$ le nombre $k$ (qui fait donc partie des diviseurs de $n$).

1. $n+7$ multiple de 5 signifie qu'il existe un entier $k$ tel que $n+7=5k$, soit $n=5k-7$.

   Les entiers naturels $n$ tels que $n+7$ soit un multiple de 5 sont les entiers $n$ s'écrivant $n=5k-7$, $k\geqslant2$.

2. $51n=17\times3n$ donc $51n$ est divisible par 17. Or, 4 n'est pas divisible par 17 donc $51n+4$ n'est pas divisible par 17.

Posons $n$ un entier relatif. Alors, $n+(n+1)+(n+2)+(n+3) = 4n+6=2(n+3)$.

On constate alors que la somme des quatre entiers consécutifs est un multiple de 2.

Avant tout, remarquons que: \[ n^2 = m^2 + 11 \iff n^2-m^2=11 \iff (n+m)(n-m)=11. \] Ainsi, il est nécessaire que $n+m$ ou $n-m$ divise 11. Or, 11 est un nombre premier donc: \[ \begin{cases} n+m = 11\\ n-m=1 \end{cases} \qquad\text{ou}\qquad \begin{cases} n-m=11\\ n+m=1 \end{cases} \]

Autrement dit, \[ n=6 \qquad \text{ et } \qquad m=5 \text{ ou }m=-5. \] Ainsi, les solutions de l'équation $n^2 = m^2 + 11$ sont les couples $\coord{6}{-5}$ et $\coord{6}{5}$.

1. Divisibilité par 2. Deux cas se présentent :

   • $p$ est pair : $p=2k$, $k\in\Z$. Dans ce cas, $p(p^2-1)=2k(4k^2-1)$ est divisible par 2.

   • $p$ est impair : $p=2k+1$, $k\in\Z$. Dans ce cas, \begin{align} p(p^2-1) & =(2k+1)\big[(2k+1)^2-1\big]\\ & = (2k+1)(4k^2+2k+1-1)\\ & = (2k+1)(4k^2+2k)\\ & = 2(2k+1)(2k^2+k). \end{align}

     Ainsi, $p(p^2-1)$ est divisible par 2.

   Dans tous les cas, le résultat est démontré.

2. Divisibilité par 3. Trois cas se présentent :

   • $p=3k$, $k\in\Z$. Alors, $p(p^2-1)=3k(9k^2-1)$ est divisible par 3.

   • $p=3k+1$. Alors,\begin{align} p(p^2-1) & = (3k+1)\big[(3k+1)^2-1\big]\\ & = (3k+1)(9k^2+6k)\\ & = 3k(3k+2)(3k+1).\end{align}

     Donc $p(p^2-1)$ est divisible par 3.

   • $p=3k+2$. Alors, \begin{align} p(p^2-1) & = (3k+2)\big[(3k+2)^2-1\big]\\ & = (3k+2)(9k^2+12k+3)\\ & = 3(3k^2+4k+1)(3k+2).\end{align}

     Donc $p(p^2-1)$ est divisible par 3.

   Dans tous les cas, $p(p^2-1)$ est divisible par 3.

$n$ est impair donc $n=2k+1$, $k\in\N$.

Ainsi, \begin{align} n^2-1 & = (2k+1)^2-1\\ & = 4k^2+4k\\ & = 4k(k+1). \end{align}

$k$ et $k+1$ sont deux entiers consécutifs donc l'un des deux est pair ; ainsi, leur produit est pair et s'écrit donc $k(k+1)=2q$, $q\in\N$.

On a donc : $n^2-1=4\times2q=8q$, ce qui prouve que $n^2-1$ est divisible par 8.

Avant tout, écrivons: \[ a|b \iff \exists k\in\Z,\ b = ka \iff n+13 = k(2n+1) \iff (2k-1)n = 13-k. \] Cela ne nous avance pas à grand-chose... Il faut donc s'y prendre autrement!

Cherchons une combinaison linéaire de $a$ et $b$ indépendante de $n$. Notons-la $pa+qb$. Comme $a|a$ et $a|b$, $a|(pa+qb)$. Comme $pa+qb$ est indépendante de $n$, cela signifie que $a$ est un diviseur de cette combinaison linéaire, et on pourra exploiter cela. \[ pa+qb = 2pn+p+qn+13q = (2p+q)n+p+13q. \] $pa+bq$ indépendante de $n$ $\iff 2p+q=0 \iff q=-2p$. On peut alors prendre $p=1$ et $q=-2$. \[ a-2b=-25. \] Par conséquent, $a|25$, donc $a\in\{-25;-5;-1;1;5;25\}$.

• si $a=-25$, alors $2n+1=-25$ et $n=-13$;
• si $a=-5$, alors $2n+1=-5$ et $n=-3$;
• si $a=-1$, alors $2n+1=-1$ et $n=-1$;
• si $a=1$, alors $2n+1=1$ et $n=0$;
• si $a=5$, alors $2n+1=5$ et $n=2$;
• si $a=25$, alors $2n+1=25$ et $n=12$.

On doit maintenant vérifier que pour toutes les valeurs de $n$ trouvées, $a$ divise $b$, ce qui se fait rapidement.

Les valeurs de $n$ cherchées sont donc : $-13$, $-3$, $-1$, 0, 2 et 12.

$a|b \iff a|(pa+qb)$, où $p$ et $q$ sont deux entiers relatifs.

$pa+qb=(p+3q)n-(4p+17q)$ est indépendante de $n$ si $p+3q=0$, soit $p=-3q$. Prenons alors $q=1$; alors $q=-3$ et: \[ pa+qb=-3a+b=-3(n-4)+3n-17=-5. \]

Ainsi, $a|(-5)$, donc il y a plusieurs cas possibles:

• $a=-1$, et dans ce cas, $n-4=-1$, soit $n=3$;
• $a=1$, et dans ce cas, $n-4=1$, soit $n=5$;
• $a=5$, et dans ce cas, $n-4=5$, soit $n=9$;
• $a=-5$, et dans ce cas, $n-4=-5$, soit $n=-1$

Ainsi, les valeurs de $n$ telles que $a$ divise $b$ sont $-1$, 3, 5 et 9.

1. On a: \begin{align} n^3+n^2+n+1 & = \dfrac{n^4-1}{n-1}\\ & = \dfrac{(n^2-1)(n^2+1)}{n-1}\\ & = \dfrac{(n-1)(n+1)(n^2+1)}{n-1}\\ & = (n+1)(n^2+1). \end{align}

   Donc $n^3+n^2+n+1$ est bien divisible par $n+1$.

2. $\numprint{1111} = 10^3+10^2+10+1$ est divisible par $10+1=11$.

   De plus, d'après la question précédente, $10^2+1=101$ est aussi un diviseur de $\numprint{1111}$.

   Deux diviseurs non triviaux de $\numprint{1111}$ sont donc 11 et 101.

1. Supposons que $n$ soit pair. Alors, il existe un entier $k$ tel que $n=2k+1$.

   Ainsi, $n^2-1=(2k+1)^2-1=(2k+1-1)(2k+1+1)=(2k)(2k+2)=4k(k+1)$.

   Par conséquent, 4 divise bien $n^2-1$.

2. Supposons que 4 divise $n^2-1$. Alors, il existe un entier $k$ tel que $n^2-1=4k$, soit $n^2=4k+1$.

   On se demande si $n$ est nécessairement impair. Supposons donc qu'il ne le soit pas, et qu'il existe un entier $p$ tel que $n=2p$.

   Alors, $n^2=4k+1 \iff 4p^2=4k+1 \iff 4(p^2-k)=1$, ce qui est impossible (car cela voudrait dire que 1 est divisible par 4).

   Ainsi, la réciproque est vraie.

1. On a: \begin{align} (n+3)(2n+5)+17 & = 2n^2+5n+6n+15+17\\ & = 2n^2+11n+32\\ & = A_n. \end{align}

2. $B_n$ divise $A_n$ si $\dfrac{A_n}{B_n}\in\Z$, pour $n\neq-3$. Or, \begin{align} \dfrac{A_n}{B_n} & =\dfrac{(n+3)(2n+5)+17}{n+3}\\ & = \dfrac{(n+3)(2n+5)}{n+3}+\dfrac{17}{n+3}\\ & =2n+5+\dfrac{17}{n+3}. \end{align}

   $(2n+5)\in\Z$ donc $\dfrac{A_n}{B_n}\in\Z\iff(n+3)\vert17$.

   17 étant un nombre premier, il n'est divisible que par 1 et 17 donc il faut que \mbox{$n+3=\pm1$} (i.e. $n=1-3=-2$ ou $n=-1-3=-4$) ou $n+3=\pm17$ (i.e. $n=17-3=14$ ou $n=-17-3=-20$).

   $B_n$ divise $A_n$ pour $n=-2$ et $n=14$.

1. On sait que $1+q+q^2+\cdots+q^n=\dfrac{1-q^{n+1}}{1-q}$ pour $q\neq1$. Ainsi, \[ 1+5+5^2+\cdots+5^{n-1}=\dfrac{1-5^n}{1-5}=\dfrac{5^n-1}{4}. \]

2. La somme $1+5+5^2+\cdots+5^{n-1}$ est entière donc $5^n-1$ est divisible par 4.

   Ainsi, $5^n-1+4k \in\N$ pour tout entier relatif $k$.

   En prenant $k=5$, on obtient $5^n-1+4\times5=5^n+19$, donc $5^n+19$ est toujours divisible par 4.

1. $x=10d+u=(7d+3d)+u=7d+(3d+u)$.

   $x$ est divisible par 7 équivaut à dire que $7d+(3d+u)$ l'est aussi, i.e. que $3d+u$ est divisible par 7 car $7d$ l'est toujours.

2. On peut s'inspirer du raisonnement précédent en posant : \begin{align} x & =392\\ & =39\times10+2\\ & =39\times(7+3)+2\\ & =39\times7+3\times39+2. \end{align}

   392 est divisible par 7 si et seulement si $3\times39+2$ l'est aussi. \[ 3\times39+2=3\times(40-1)+2=120-3+2=119. \] On recommence avec 119 : \[ 119=11\times7+11\times3+9. \] 119 est divisible par 7 si et seulement si $11\times3+9$ l'est aussi. \[ 11\times3+9=33+9=42=7\times6. \] Ainsi, 119 est divisible par 7, donc 392 aussi.

3. $611\times3+9=\numprint{1833}+9=\numprint{1842}$.

   $184\times3+2=552+2=554$

   $55\times3+4=165+4=169$

   $16\times3+9=48+9=57$

   $57$ n'est pas divisible par 7 donc $\numprint{6119}$ non plus.

1. $a\in\N$.

   \begin{align} a^5-a & = a(a^4-1)\\ & = a(a^2-1)(a^2+1)\\ & = a(a-1)(a+1)(a^2+1). \end{align}

   Entre $a$ et $a+1$, il y a un nombre pair ; donc $a^5-a$ est divisible par 2.

   $a-1$, $a$ et $a+1$ sont trois nombres consécutifs. Si l'un deux est divisible par 5, alors $a^5-1$ l'est aussi et donc au final, il est divisible par 10.

   Si aucun des nombres $a-1$, $a$ et $a+1$ n'est divisible par 5, alors notons $r$ le reste de la division euclidienne de $a$ par 5 : $a=5q+r$, $0

   Si $a-1$ n'est pas divisible par 5, alors $r\neq1$ ;

   si $a+1$ n'est pas divisible par 5, alors $r\neq4$.

   Alors, $a^2+1=(5q+r)^2+1=25q^2+10qr+r^2+1$, avec $r=2$ ou $r=3$.

   • Si $r=2$, $r^2+1=5$ ;

   • Si $r=3$, $r^2+1=10$.

   Dans les deux cas, $a^2+1$ est divisible par 5.

   Ainsi, $a^5-a$ est divisible par 5 et par 2, donc par 10.

2. $a^5-b^5$ divisible par 10.

   Or, on peut écrire : \[ a^5-b^5 = a^5-a+a-(b^5-b)-b=(a^5-a)-(b^5-b)+(a-b). \]

   $a^5-a$ et $b^5-b$ sont divisibles par 10 d'après la question précédente ; ainsi, si $a^5-b^5$ est divisible par 10, $a-b$ doit l'être aussi.

   Ainsi, $a-b=10q$, $q\in\N$ et donc $a=10q+b$. En ajoutant $b$ dans les deux membres, on obtient $a+b=10q+2b=2(5q+b)$, et donc $a+b$ est divisible par 2.

   $a-b$ est divisible par 10 et $a+b$ est divisible par 2, donc $(a-b)(a+b)=a^2-b^2$ est divisible par 20.

1. Supposons que $d$ divise $a=12n+7$ et $b=3n+1$. Alors, $d$ divise toute combinaison linéaire de $a$ et $b$: \[ \forall\coord{\lambda}{\mu}\in\Z^2,\ d | \lambda(12n+7)+\mu(3n+1). \] Choisissons $\coord{\lambda}{\mu}$ de sorte que la combinaison linéaire de dépende plus de $n$. Prenons alors $\lambda=1$ et $\mu=-4$.

   Alors, $d$ divise $12n+7-4(3n+1)$, soit $d$ divise 3.

2. Faisons un raisonnement par l'absurde: supposons que $\dfrac{12n+7}{3n+1}$ ne soit pas irréductible.

   Alors, il existe un enter $d$ qui divise $12n+7$ et $3n+1$, donc qui divise 3 (d'après la question précédente).

   Ainsi, $d=1$ ou $d=3$ ou $d=-1$ ou $d=-3$.

   Les cas $d=1$ et $d=-1$ ne sont pas possibles car la fraction est supposée simplifiable.

   Si $d=3$ ou $d=-3$ alors 3 divise $12n+7$, ce qui est impossible car 3 divise $12n$ mais pas 7.

   Il y a donc contradiction; notre hypothèse de départ est alors fausse: $\dfrac{12n+7}{3n+1}$ est irréductible.

Remarquons que : \[ \fact{\numprint{1000}}=(1\times2\times3\times\cdots\times10)\times(11\times\cdots\times20)\times\cdots\times(991\times\cdots\times\numprint{1000})\;. \]

Combien de multiples de 3 avons-nous ici ? Il y en a 333 ($999\div3$).

On peut donc factoriser ainsi : \begin{align} \fact{\numprint{1000}} & =3^{333}( 1\times2\times\textcolor{red}{1}\times 4\times5\times\textcolor{red}{2}\times 7\times8\times\textcolor{red}{3}\times10)\times \cdots\times(991\times992\times\textcolor{red}{331}\cdots\times\textcolor{red}{333}\times\numprint{1000})\\ & = 3^{333} \times \textcolor{red}{1\times2\times\cdots\times333}\times\underbrace{1\times2\times4\times5\times\cdots\times\numprint{1000}}_{\text{aucun multiples de 3}}\\ & = 3^{333} \times \fact{333} \times N_1,\quad \text{avec $N_1$ non multiple de 3}. \end{align}

De plus, dans $\fact{333}$, il y a 111 multiples de 3 donc, avec un même raisonnement, on a : \[ \fact{333}=3^{111} \times \fact{111} \times N_2,\quad\text{avec $N_2$ non multiple de 3}. \] On voit apparaître \fact{111} dans lequel il y a 37 multiples de 3 (3, 6, 9, ..., 99, 102, 105, 108, 111). On peut donc écrire : \[ \fact{111} = 3^{37} \times \fact{37} \times N_3,\quad\text{avec $N_3$ non multiple de 3}. \] De même, on voit \fact{37} apparaître, où il y a 12 multiples de 3 donc on peut écrire : \[ \fact{37} = 3^{12} \times \fact{12} \times N_4,\quad\text{avec $N_4$ non multiple de 3}. \] On voit \fact{12} apparaître, où il y a 4 multiples de 3 donc on peut écrire : \[ \fact{12} = 3^{4} \times \fact{4} \times N_5,\quad\text{avec $N_5$ non multiple de 3}. \] On voit apparaître \fact{4} où il y a 1 multiple de 3 et on peut écrire : \[ \fact{4}=3^1(1\times2\times1\times4)\;. \] Finalement, dans $\fact{\numprint{1000}}$, on peut mettre en facteur $3^{333+111+37+12+4+1}=3^{498}$.

Ainsi, le plus grand entier $n$ tel que $3^n$ divise $\fact{\numprint{1000}}$ est $n=498$.

1. $345 = 28\times12 + 9$.
2. $76=1\times67+9$.
3. $\numprint{1001} = 9\times101 + 92$.
4. $673=6\times97+91$.

>>> 345//12
28

>>> 345%12
9

On écrit $a=bq+r$ avec $a=7n+5$ et $b=3n+1$: \[ 7n+5 = 2(3n+1) + n+3\qquad,\qquad 0 \leqslant n+3 < 3n+1. \] La condition sur le reste $0 \leqslant n+3 < 3n+1$ équivaut à écrire que $n > 1$. Donc,

• si $n>1$ le quotient est égal à 2 et le reste à $n+3$;
• si $n=0$, $a=bq+r \iff 5 = 5\times1+0$ donc dans ce cas, le quotient est égal à 5 et le reste à 0;
• si $n=1$, $a=bq+r \iff 12 = 3\times4 + 0$ donc ici, le quotient est égal à 3 et le reste à 0.

D'après l'énoncé, on a : \begin{cases} n = 4q+ 3\\ n = 5q+1 \end{cases} donc $4q+3=5q+1 \iff q = 2$.

Par conséquent, $n=4q+3=11$.

1. Le reste de la division euclidienne de $n$ par 17 est égal à 7: \[ n = 17q + 7. \] Par conséquent, \begin{align} n^2 & = (17q+7)^2\\ & = 17^2q^2 + 17\times14q + 49\\ & = 17(17q^2+14q) + 17\times2 + 15\\ & = 17(17q^2+14q+2) + 15. \end{align}

   On s'est ici arrangé pour écrire $n^2$ sous la forme $17Q + r$, $0\leqslant r < 17$, afin d'avoir une division euclidienne.

   Ainsi, le reste de la division euclidienne de $n^2$ par 17 est 15.

2. Procédons de même avec $n^3$: \begin{align} n^3 & = (17q+7)^3\\ & = 17^3q^3 + 3\times17^2\times q^2\times7 + 3\times17q\times 7^2 + 7^3\\ & = 17(17^2q^3 + 3\times17\times7q^2 + 3q\times7^2) + 20*17 + 3\\ & = 17(289q^3+357q^2+147q+20)+3.\end{align}

   Ainsi, le reste de la division euclidienne de $n^3$ par 17 est 3.

1. On a: \begin{align} 10^2=100 & =9\times11+1\\ 10^3=\numprint{1000} & = 90\times11+10\\ 10^4=\numprint{10000} & = 909\times11+1\\ 10^5=\numprint{100000} & =\numprint{9090}\times11+10. \end{align}

   On peut conjecturer que lorsque $n$ est pair, le reste de la division euclidienne de $10^n$ par 11 est égal à 1 et lorsqu'il est impair, ce reste est égal à 10.

2. • Supposons que $n$ soit un entier naturel pair. Alors, $n=2k$, $k\in\N$ et $10^n=10^{2k}=100^k=(99+1)^k$.

     Or, $(a+b)^k=\displaystyle\sum_{p=0}^k c_p a^p b^{k-p}$, où les $c_p$ sont des coefficients entiers.

     Autrement dit, $(99+1)^k=99^k+99^{k-1}c_1+99^{k-2}c_2+\cdots+99c_{p-1}+1$.

     Chaque terme de cette somme (sauf le dernier) étant un multiple de 99, le reste de la division euclidienne de $100^k$ par 11 est égale à 1 (le dernier terme de la somme).

     Cela montre que si $n$ est pair, alors le reste de la division euclidienne de $10^n$ par 11 est égal à 1.

   • Supposons que $n$ soit impair. Alors, $n=2k+1$, $k\in\N$ et $10^n=10^{2k+1}=10^{2k}\times10$.

     D'après ce qui a été fait précédemment, on peut alors écrire : \[ 10^{2k}\times10=10\times99^k+10\times99^{k-1}c_1+10\times99^{k-2}c_2+\cdots+10\times99c_{p-1}+10. \]

     Ainsi, le reste de la division euclidienne de $10^{2k+1}$ par 11 est égal à 10.

   La conjecture est alors démontrée.

Voici une suggestion, qui fait appel aux listes construites par compréhension:

L = [ 2*q+1 for q in range(50) ]
P = [ 3*q+2 for q in range(33) ]
Q = [ 5*q+4 for q in range(20) ]
N = [ n for n in L if n in P and n in Q ]
print( N )

[29, 59, 89]

La liste $\texttt{L}$ est construite en prenant tous les entiers naturels $q$ de 0 à 49 ($\texttt{range(0,50}$), et en ajoutant 1 à leur double. $2\times49+1=99$ et $2\times50+1=101>100$, ce qui justifie que l'on prend $q\leqslant49$.

Cette liste contient alors tous les entiers de 0 à 100 dont le reste est 1 dans la division euclidienne par 2.

Vous l'aurez compris, les listes $\texttt{P}$ et $\texttt{Q}$ sont construites sur un modèle similaire par rapport aux conditions de l'énoncé sur les autres divisions euclidiennes.

La liste $\texttt{N}$ contient toutes les valeurs de $n$ dans $\texttt{L}$ qui sont aussi dans les autres listes. C'est donc l'intersection des trois listes, et c'est ce que nous voulions.

Une autre suggestion est la suivante:

for n in range(101): if n%2 == 1 and n%3 == 2 and n%5 == 4: print(n)

qui affiche les mêmes nombres (29, 59 et 89).

Ici, on fait une simple boucle pour parcourir tous les entiers naturels de 0 à 100, et on teste pour chacun d'eux leur reste dans la division euclidienne par 2, 3 et 5. S'ils coïncident avec ce que l'on veut, on les affiche.

$13\equiv-1\mod14$ donc $13^{\numprint{1789}}\equiv(-1)^{\numprint{1789}}\equiv-1\equiv13\mod14$.

Le reste de la division euclidienne de $13^{\numprint{1789}}$ par 14 est donc 13.

Nous savons que $32=4\times7+4$ donc $32\equiv4\mod7$.

Ainsi, $32^{45}\equiv4^{45}\mod7$.

Or, $4^2=16\equiv2\mod7$ et $4^3=64\equiv1\mod7$.

On peut donc écrire : \begin{align} 32^{45} & \equiv4^{3\times15}\mod7\\ & \equiv\big(4^3\big)^{15}\mod7\\ & \equiv1^{15}\mod7\\ & \equiv1\mod7. \end{align}

Le reste de la division euclidienne de $32^{45}$ par 7 est donc 1.

Remarquons que $24\equiv3\mod7$ car $24=3\times7+3$.

Ainsi, \begin{align} 24^1\equiv3^1\equiv3\mod7\\ 24^2\equiv3^2\equiv2\mod7\\ 24^3\equiv3^3\equiv6\mod7\\ 24^4\equiv3^4\equiv4\mod7\\ 24^5\equiv3^5\equiv5\mod7\\ 24^6\equiv3^6\equiv1\mod7\\ 24^7\equiv3^7\equiv3\mod7\end{align}

La boucle est bouclée pour l'exposant 7 et on peut en conclure que $24^{6k+1}\equiv3\mod7$, où $k\in\N$.

Ainsi, le reste de la division euclidienne de $24^n$ par 7 est égal à 3 pour $n\equiv1\mod6$.

$a$ n'est pas divisible par 3 donc $a\equiv1\mod3$ ou $a\equiv2\mod3$.

Ainsi, $a^6\equiv1^6\equiv1\mod3$ ou $a\equiv2^6\equiv64\equiv1\mod3$ car $64=3\times21+1$.

Ainsi, $a^6-b^6\equiv1-1\equiv0\mod3$ et donc $a^6-b^6$ est divisible par 3.

Nous avons: \[ $\left. \begin{array}{l} n\equiv1\mod2\iff21n\equiv21\mod42\\ n\equiv2\mod3\iff14n\equiv28\mod42\\ n\equiv5\mod7\iff6n\equiv30\mod42 \end{array}\right\rbrace\Rightarrow 41n\equiv79\mod42 \]

Or, $41\equiv-1\mod42$ et $79\equiv-5\mod42$ donc $-n\equiv-5\mod42$, soit $n\equiv5\mod42$.

Le reste de la division euclidienne de $n$ par 42 est donc égal à 5.

On sait que $10 \equiv 1 \mod 3$ donc: \[ \forall k\in\N,\qquad 10^k \equiv 1 \mod 3 \] et donc: \[ \sum_{k=0}^n x_k \times 10^k \equiv \sum_{k=0}^n x_k \mod 3. \]

\begin{align} x \text{ est divisible par 3 } & \iff x\equiv 0 \mod 3\\[8pt] & \iff \sum_{k=0^N} x_k \equiv 0 \mod 3\\[8pt] & \iff \text{ la somme des chiffres de x divise 3}. \end{align}

$10 \equiv 1 \mod 9$ donc le critère de divisibilité par 9 est identique: un nombre est divisible par 9 si la somme de ses chiffres l'est aussi.

On a : \begin{align} 1a4b\text{ divisible par 45} & \iff 1a4b\text{ divisible par 5 et 9}\\[10pt] & \iff 1a4b \equiv 0 \mod 5\text{ et }1a4b\equiv0\mod9\\[10pt] & \iff b=0\text{ ou }b=5\text{ et }1+a+4+b\equiv0\mod9\\[10pt] & \iff b=0\text{ ou }b=5\text{ et }a+b\equiv-5\equiv4\mod9. \end{align}

• si $b=0$ alors $a=4$;
• si $b=5$ alors $a=8$.

Les deux nombres possibles sont alors $1845$ et $1440$.

Pour contrôler nos résultats, on va utiliser le programme suivant.

Dans ce programme, on va se servir de la conversion des nombres en chaîne de caractères: si $\texttt{n}$ est un objet de type $\texttt{int}$ (entier) alors $\texttt{str(n)}$ est le même nombre, mais vu comme une chaîne de caractères, où $\texttt{str(n)[0]}$ est le premier chiffre en partant de la gauche.

>>> for n in range(10000):
	if n%45==0 and str(n)[0]=='1' and str(n)[2]=='4':
		print(n)

1440
1845

Soit $n$ un entier naturel.

$3^2 = 9 \equiv 2 \mod 7$ donc $\big(3^2\big)^n \equiv 2^n \mod 7$, soit $3^{2n}\equiv 2^n \mod 7$.

On en déduit alors que $3^{2n}-2^n \equiv 0\mod 7$, et donc que $3^{2n}-2^n$ est divisible par $n$.

\begin{align} 11 | (7x+4y) & \iff 7x+4y \equiv 0 \mod 11\\ & \iff {\color{red}8\times}(7x+4y) \equiv 0 \mod 11\\ & \iff 56x + 32y \equiv 0 \mod 11\\ & \iff x + 10y \equiv 0 \mod 11 \quad\text{ car }56\equiv1\mod11\text{ et }32\equiv10\mod11. \end{align}

Remarquons que: \[ 73 \equiv 3\quad (5) \] donc: \[ 73^{37} \equiv 3^{37}\quad (5). \]

Regardons les premières puissances de 3 modulo 5:

• $3^1\equiv 3\quad (5)$
• $3^2\equiv 9\equiv 4 \quad (5)$
• $3^3\equiv 27 \equiv 2\quad (5)$
• $3^4\equiv \big(3^2\big)^2 \equiv 4^2 \equiv 1\quad (5)$

Ce dernier reste est intéressant car il signifie que $\big(3^4\big)^k\equiv 1\quad (5)$ pour tout entier naturel $k$.

Or, \[ 3^{37} = 3^{4\times 9 + 1} \] donc: \[ 73^{37} \equiv 3^{4\times9+1}\quad (5) \] soit: \[ 73^{37} \equiv \big(3^{4}\big)^9 \times 3^1\quad (5) \] donc: \[ 73^{37} \equiv 1 \times 3^1\quad (5). \] Finalement, \[ \boxed{73^{37} \equiv 3\quad (5).} \] Ainsi, le reste de la division euclidienne de $73^{37}$ par 5 est 3.

$17\equiv3\mod7$ car $17=2\times7+3$. Ainsi, $17^2\equiv3^2\equiv2\mod7$, et donc $17^{\textcolor{red}{6}}\equiv2^3\equiv1\mod7$.

On écrit 548 sous la forme : $548=\textcolor{red}{6}\times91+2$ donc : \begin{align} 17^{548} & =\big(17^6\big)^{91}\times17^2\\ & \equiv 1^{91}\times2\mod7\\ & \equiv 2\mod 7. \end{align}

Ainsi, le reste de la division euclidienne de $17^{548}$ par 7 est égal à 2.

1. On cherche $x$ tel que $5x\equiv1\mod7$. On constate que : \begin{cases} 5\times1\equiv5\mod7\\ 5\times2\equiv3\mod7\\ 5\times3\equiv1\mod7 \end{cases}

   Donc, si $x\equiv3\mod7$ alors $5x\equiv5\times3\equiv1\mod7$.

   De plus, si $5x\equiv1\mod7$ alors $3\times5x\equiv3\mod7$, soit $15x\equiv3\mod7$ donc $x\equiv3\mod3$.

   On a alors l'équivalence suivante : $x\equiv3\mod7\iff5x\equiv1\mod7$.

   Par conséquent, les inverses de 5 modulo 7 sont toutes les valeurs de $x$ telles que $x\equiv3\mod7$.

2. On cherche $x$ tel que $3x\equiv1\mod5$.

   On constate que : \begin{cases} 3\times1\equiv3\mod5\\ 3\times2\equiv1\mod5 \end{cases}

   On peut alors raisonner de la même façon qu'à la question précédente.

   Par conséquent, un inverse de 3 modulo 5 sont toutes les valeurs de $x$ telles que $x\equiv2\mod5$.

3. On cherche $x$ tel que $6x\equiv1\mod15$.

   On constate que : \begin{cases} 6\times1\equiv6\mod15\\ 6\times2\equiv12\mod15\\ 6\times3\equiv3\mod15\\ 6\times4\equiv9\mod15\\ 6\times5\equiv0\mod15\\ 6\times6\equiv6\mod15 \end{cases}

   On constate alors que c'est un cas particulier : \begin{cases} 6\times(1+5k)\equiv1\mod15,\ k\in\N\\ 6\times(2+5k)\equiv12\mod15,\ k\in\N\\ 6\times(3+5k)\equiv3\mod15,\ k\in\N\\ 6\times(4+5k)\equiv9\mod15,\ k\in\N\\ 6\times(5+5k)\equiv0\mod15,\ k\in\N \end{cases}

   Par conséquent, il n'existe pas d'inverse à 6 modulo 15.

   Cela vient du fait que 6 et 15 ne sont pas premiers entre eux.

Supposons que 7 divise $a^2+b^2$.

Les restes possibles de la division euclidienne de $a$ par 7 sont : 0, 1, 2, 3, 4, 5 ou 6.

\begin{align} a\equiv0\mod 7&\Rightarrow a^2\equiv0\mod7\\ a\equiv1\mod 7&\Rightarrow a^2\equiv1\mod7\\ a\equiv2\mod 7&\Rightarrow a^2\equiv4\mod7\\ a\equiv3\mod 7&\Rightarrow a^2\equiv9\equiv2\mod7\\ a\equiv4\mod 7&\Rightarrow a^2\equiv16\equiv2\mod7\\ a\equiv5\mod 7&\Rightarrow a^2\equiv25\equiv4\mod7\\ a\equiv6\mod 7&\Rightarrow a^2\equiv36\equiv1\mod7\end{align}

Il n'y a donc que 4 restes possibles dans la division euclidienne de $a^2$ par 7 : 0, 1, 2 ou 4.

Il en est de même pour $b^2$.

Or, $a^2+b^2\equiv0\mod7$ donc seul le couple $\coord{0}{0}$ convient.

Ainsi $a\equiv0\mod7$ et $b\equiv0\mod7$, soit 7 divise $a$ et $b$.

La réciproque est vraie car si 7 divise $a$ et $b$, alors $a^2\equiv0\mod7$ et $b^2\equiv0\mod7$, donc $a^2+b^2\equiv0\mod7$.

\begin{align} x^2\equiv-11\mod100 & \iff x^2\equiv300-11\mod100\\ & \iff x^2\equiv289\mod100\\ & \iff x^2\equiv17^2\mod100\\ & \iff x^2-17^2\equiv0\mod100\\ & \iff (x-17)(x+17)\equiv0\mod100\\ & \iff x\equiv17\mod100\qquad\text{ou}\qquad x\equiv-17\mod100\\ & \iff \boxed{x\equiv17\mod100 \qquad\text{ou}\qquad x\equiv83\mod100} \end{align}

1. • Initialisation : $4^0=1$ et $1+3\times0=1$ donc $4^n\equiv1+3n\mod9$ est vraie pour $n=0$.

   • Hérédité : supposons que pour un entier $n$ fixé, $4^n\equiv1+3n\mod9$.

     Alors, $4^{n+1}\equiv4\times(1+3n)\mod9$, soit $4^{n+1}\equiv4+12n\equiv4+3n\equiv1+3(n+1)\mod9$.

     L'hérédité est alors vérifiée.

   Ainsi, pour tout entier naturel $n$, $4^n\equiv1+3n\mod9$.

2. On a: \begin{align} 2^{2n}+15n-1 & \equiv4^n+15n-1\mod9\\ & \equiv1+3n+15n-1\mod9\\ & \equiv18n\mod9\\ & \equiv0\times n\mod9\\ & \equiv0\mod9. \end{align}

Posons: \[ {\cal P}_n \quad : \quad (n+1)(n+2)\cdots(2n-1)\times2n\equiv0\mod 2^n. \]

Notons: \[ A_n=(n+1)(n+2)\cdots(2n-1)\times2n. \]

Montrons par récurrence que ${\cal P}_n$ est vraie pour tout entier naturel $n$.

• Initialisation : ${\cal P}_0$ est vraie car $A_0=1$ et $2^0=1$. On a donc bien $A_0\equiv0\mod1$.

• Hérédité : Supposons que pour un entier $n$ fixé, ${\cal P}_n$ est vraie, donc que $A_n=2^nB_n$.

  \begin{align} A_{n+1} & = A_n\times(2n+1)(2n+2)\\[8pt] & = 2^nB_n\times2(2n+1)(n+1)\\[8pt] & = 2^{n+1}B_n(2n+1)(n+1).\end{align}

  Ainsi, $A_{n+1}$ est divisible par $2^{n+1}$. L'hérédité est alors vérifiée.

Ainsi, ${\cal P}_n$ est vraie pour tout entier naturel $n$.

$A_n=\dfrac{(2n)!}{n!}$ donc $\dfrac{A_n}{2^n}=\dfrac{(2n)!}{2^n(n!)}=1\times3\times5\times\cdots\times(2n-1)$.

Le quotient de $A_n$ par $2^n$ est donc égal à $\displaystyle\prod_{k=0}^{n-1}(2k+1)$.