Divisibilité par combinaison linéaire

1. Idée : un tableau des six restes. Si $a\equiv 0,1,2,3,4,5 \pmod 6$, alors $a^2\equiv 0,1,4,9,16,25$, soit $a^2\equiv 0,\ 1,\ 4,\ 3,\ 4,\ 1 \pmod 6$. Les restes possibles de $a^2$ sont $0$, $1$, $3$ et $4$.

2. Avec le même tableau, $a^3\equiv 0,1,8,27,64,125\equiv 0,1,2,3,4,5\equiv a \pmod 6$. Autre voie : $a^3-a=(a-1)a(a+1)$ est le produit de trois entiers consécutifs, divisible par $2$ et par $3$, donc par $6$ (car $\pgcd(2,3)=1$). Ainsi $6$ divise $a^3-a$.

3. Idée : l'hérédité multiplie par $a^2$ puis utilise $a^3\equiv a$. Initialisation : $a^1\equiv a$. Hérédité : si $a^{2n+1}\equiv a$, alors $a^{2n+3}=a^{2n+1}\cdot a^2\equiv a\cdot a^2=a^3\equiv a \pmod 6$. La propriété est vraie pour tout $n\in\N$.

1. Idée : une relation $ux+vy=1$ est une relation de Bézout. L'égalité admise s'écrit $1\cdot(a^2+a-1)+(1-a)\cdot(a+2)=1$ : d'après le théorème de Bézout, $\pgcd(a+2,\ a^2+a-1)=1$.

2. La relation donne $(a+2)(a-1)\equiv -1$, donc $(a+2)(1-a)\equiv 1 \pmod{a^2+a-1}$ : $1-a$ est un inverse de $a+2$. Si $(a+2)n\equiv 1$, en multipliant par $1-a$ : $n\equiv 1-a$. Réciproquement $n\equiv 1-a$ convient. Les solutions sont les entiers $n\equiv 1-a \pmod{a^2+a-1}$.

3. Pour $a=3$ : $a+2=5$, $a^2+a-1=11$ et $1-a=-2$. Les solutions de $5n\equiv 1 \pmod{11}$ sont $n\equiv -2\equiv 9 \pmod{11}$ ; vérification : $5\times 9=45=4\times 11+1$.

1. Idée : remplacer $a$ par son reste $-2$ dans le polynôme. $d\mid a+2\iff a\equiv-2\pmod d$. Les congruences se multiplient et s'additionnent : $a^2+a-1\equiv(-2)^2+(-2)-1=4-2-1=1\pmod d$. $\boxed{a^2+a-1\equiv1\pmod d}$

2. Idée : un diviseur commun $d\geq2$ contredirait la question 1. Soit $d=\mathrm{pgcd}(a+2,\,a^2+a-1)$. Si $d\geq2$, alors $d\mid a+2$ donc $a^2+a-1\equiv1\pmod d$, mais aussi $d\mid a^2+a-1$ donc $a^2+a-1\equiv0\pmod d$ ; d'où $1\equiv0\pmod d$, c'est-à-dire $d\mid1$, absurde. Donc $d=1$ : les deux entiers sont premiers entre eux. (Autre lecture : $a^2+a-1=(a+2)(a-1)+1$, identité de la division euclidienne.)

3. Idée : appliquer. $a=10$ : $\dfrac{109}{12}$ ; $109=12\times9+1$, et d'après 2 le pgcd vaut $1$ : la fraction est déjà irréductible.

1.a $7\times15-26\times4=105-104=1$.

1.b Idée : lemme de Gauss. Si $7x-26y=1$, alors $7(x-15)=26(y-4)$ ; $26$ divise $7(x-15)$ et $\pgcd(7,26)=1$, donc $x=15+26k$, puis $y=4+7k$, $k\in\Z$. Réciproquement, $7(15+26k)-26(4+7k)=105-104=1$. Les solutions de l'équation $(E)$ sont les couples $(15+26k,\ 4+7k)$, $k\in\Z$.

1.c Idée : $7x\equiv1\pmod{26}$ signifie qu'il existe un entier $y$ tel que $7x-26y=1$. D'après 1.b, $7x\equiv1\pmod{26}$ si et seulement si $\boxed{x\equiv15\pmod{26}}$ : $15$ est un inverse de $7$ modulo $26$.

2.a F a pour rang $5$ : $7\times5+3=38=26+12$, donc $m=12$, qui est le rang de M.

2.b I : $7\times8+3=59\equiv7$, lettre H ; N : $7\times13+3=94\equiv16$, lettre Q ; F donne M ; O : $7\times14+3=101\equiv23$, lettre X. Le mot INFO est codé $\boxed{\text{HQMX}}$.

3.a Idée : pour « diviser » par $7$ modulo $26$, on multiplie par son inverse $15$. Si $7n+3\equiv m$, alors $7n\equiv m-3$, et en multipliant par $15$ : $105n\equiv15m-45\pmod{26}$. Or $105=4\times26+1$ et $-45=-2\times26+7$, donc $n\equiv15m+7\pmod{26}$. Réciproquement, si $n\equiv15m+7$, alors $7n+3\equiv105m+52\equiv m\pmod{26}$, car $105\equiv1$ et $52\equiv0$.

3.b Si deux lettres de rangs $n$ et $n'$ ont le même code $m$, alors d'après 3.a, $n\equiv15m+7\equiv n'\pmod{26}$ ; comme $0\leq n,n'\leq25$, on a $n=n'$. Pour décoder une lettre de rang $m$, on calcule le reste de $15m+7$ modulo $26$ et on lit la lettre de ce rang.

3.c J : $15\times9+7=142=5\times26+12$, lettre M ; D : $15\times3+7=52\equiv0$, lettre A ; G : $15\times6+7=97=3\times26+19$, lettre T ; A : $15\times0+7=7$, lettre H. Le mot codé JDGA est $\boxed{\text{MATH}}$.