Arithmétique dans ℤ

Pour $a,b\in \mathbb{Z}$ avec $b\ne 0$, on dit que $b$ divise $a$, noté $b|a$, s'il existe $k\in \mathbb{Z}$ tel que $a=bk$.

• $a|a$, $1|a$, $a|0$ pour tout $a\ne 0$.
• Si $a|b$ et $b|c$, alors $a|c$.
• Si $a|b$ et $a|c$, alors $a|(ub+vc)$ pour tous $u,v\in \mathbb{Z}$.
• Si $a|b$ et $b\ne 0$, alors $|a|\le |b|$.

Soient $a\in \mathbb{Z}$ et $b\in {\mathbb{Z}}^{\ast }$. Il existe un unique couple $(q,r)\in \mathbb{Z}\times \mathbb{N}$ tel que :

Pour $a,b\in \mathbb{Z}$ non tous deux nuls, le $\mathrm{PGCD}(a,b)$ est le plus grand entier positif divisant à la fois $a$ et $b$.

Si $a=bq+r$, alors $\mathrm{PGCD}(a,b)=\mathrm{PGCD}(b,r)$. En itérant, on arrive à un reste nul ; le dernier reste non nul est le PGCD.

$a,b\in \mathbb{Z}$ sont premiers entre eux si $\mathrm{PGCD}(a,b)=1$.

Si $a,b$ sont premiers entre eux, il existe $u,v\in \mathbb{Z}$ tels que $ua+vb=1$.

Si $a|bc$ et $a$ premier avec $b$, alors $a|c$.

Un entier $p>1$ est premier si ses seuls diviseurs positifs sont $1$ et $p$.

Tout entier $n\ge 2$ s'écrit de manière unique (à l'ordre près) comme produit de nombres premiers.

Si $a=\prod p_i^{{\alpha }_i}$ et $b=\prod p_i^{{\beta }_i}$ :

Et $\mathrm{PGCD}(a,b)\times \mathrm{PPCM}(a,b)=|ab|$.

Pour $n\in {\mathbb{N}}^{\ast }$, on dit que $a\equiv bmodn$ (lu « $a$ congru à $b$ modulo $n$ ») si $n|(b-a)$. C'est une relation d'équivalence.

Si $a\equiv a^{\prime }modn$ et $b\equiv b^{\prime }modn$ :

• $a+b\equiv a^{\prime }+b^{\prime }modn$.
• $ab\equiv a^{\prime }{b}^{\prime }modn$.
• Pour tout $k\in \mathbb{N}$, $a^k\equiv a^{\prime k}modn$.

Modulo $7$ : $10\equiv 3mod7$. Donc $10^3=1000\equiv 3^3=27\equiv 6mod7$ (car $27=7\times 3+6$).

Démontrer que $7|(2^{3n}-1)$ pour tout $n\in \mathbb{N}$. En effet $2^3=8\equiv 1mod7$, donc $2^{3n}=(2^3{)}^n\equiv 1^n=1mod7$.