Preuve.

Unicité :
Supposons qu'il existe deux couples d'entiers \((q,r)\) tel que \(a=bq+r\) avec \(0 \leq r < |b|\) et \((q',r')\) tel que \(a=bq'+r'\) avec \(0 \leq r' < |b|\).
On a donc \(b(q-q')=r-r'\).
D'où \(|b||q-q'|=|r-r'|<|b|\). Comme \(b\neq0\), on obtient \(|q-q'|<1\). \(q\) et \(q'\) étant des entiers, on obtient que \(q=q'\).
D'où \(a-bq=a-bq'=r=r'\).
Ainsi l'unicité est vérifiée.

Existence :
Supposons \(b>0\):
Posons l'ensemble \(A=\{m\in\mathbb{Z} \text{ , } mb \leq a\}\).
\(A\) est non vide et majoré, ainsi il admet un plus grand élément qu'on note \(q\).
Posons \(r=a-bq\).
Comme \(q\in A\), on \(bq\leq a\) donc \(r \geq 0\). De plus, \((q+1)b \notin A\). Donc \((q+1)b>a\).
Ainsi, \(b>a-bq\) i.e. \(r Si \(b<0\), on applique le même raisonnement à \(-b\).
Ainsi l'existence est vérifiée.
Ce qui achève la démonstration.

Preuve.

Si \(b|a\) alors il existe \(k\) un entier tel que \(a=bk + 0\).
Donc par unicité de la division euclidienne, le reste est nul.

Réciproquement si le reste est nul alors il existe \(q\) un entier tel que \(a=bq+0\) ce qui revient à dire que \(b|a\).

Preuve.

1. Si \(a|b\) et \(c|d\) donc il existe \(k,k'\in\mathbb{Z}\) tels que \(b=ka\) et \(d=k'c\). D'où \(bd=kk'ac\).
En posant \(k"=kk'\), on a, \(k"\in\mathbb{Z}\). Ainsi \(bd=k"ac\), i.e \(ac|bd\).

2. Si \(a|b\) et \(a|c\) donc il existe \(k,k'\in\mathbb{Z}\) tels que \(b=ka\) et \(c=k'a\).
Soient \(u,v \in\mathbb{Z}\), \(bu +cv=uka + vk'a\), i.e \(bu +cv=(uk + vk')a\), or \(uk + vk'\in\mathbb{Z}\). Donc par définition, \(a|bu +cv\).

3. Soit \(c \neq 0\).
Si \(ac|bc\), donc il existe \(k,\in\mathbb{Z}\) tel que \(bc=kac\). Comme \(c \neq 0\) alors obtient \(b=ka\) i.e \(a|b\).
Si \(a|b\) alors il existe \(k,\in\mathbb{Z}\) tel que \(b=ka\). Ainsi en multipliant par c, on a \(bc=kac\), i.e \(ac|bc\).

Preuve.

1. Si \(a \equiv b\ [n]\) et \(c \equiv d\ [n]\). Alors il existe \(k,k'\in\mathbb{Z}\) tels que \(nk=b-a\) et \(nk'=d-c\).
D'où \(n(k-k')=(b+d)-(a+c)\), i.e \(a+c \equiv b+d\ [n]\).

2. Si \(a \equiv b\ [n]\) et \(c \equiv d\ [n]\), alors il existe \(k,k'\in\mathbb{Z}\) tels que \(nk+b=a\) et \(nk'+d=c\).
D'où \(n\underbrace{(nkk'+k'b+kd)}_{\in\mathbb{Z}}}+bd\). D'où \(ac \equiv bd\ [n]\).

3. \(a=a+n\times0\). Ainsi \(a \equiv a\ [n]\)

4. Si \(a=nk+b\) donc \(a-nk=b\). Ainsi en posant \(k'=-k\), on a \(a+nk'=b\) i.e \(b \equiv a\ [n]\).

5. Si \(a=nk+b\) et \(b=nk'+c\), alors \(a=nk+nk'+c\), i.e \(a=n\underbrace{(k+k')}_{\in\mathbb{Z}}+c\) i.e \(a \equiv c\ [n]\).

Preuve.

Notons \(D(a,b)\) l'ensemble des diviseurs communs à \(a\) et \(b\).
Montrons par double inclusion que \(D(a,b) = D(b,r)\).
Si \(d \in D(a,b)\), alors \(d\) divise \(a\) et \(b\) donc \(d\) divise toutes combinaisons linéaires de \(a\) et \(b\) ainsi \(d\) divise \(a-bq=r\). D'où \(d \in D(b,r)\).
Si \(d \in D(b,r)\) alors \(d\) divise \(b\) et \(r\) donc \(d\) divise toutes combinaisons linéaires de \(b\) et \(r\) ainsi \(d\) divise \(bq+r=a\). D'où \(d \in D(a,b)\).
Ainsi \(D(a,b) = D(b,r)\). Ainsi, ces deux ensembles le même plus grand élément.
Donc \(\boxed{a\wedge b = b\wedge r}\).

Preuve.

Si on a \(au+bv=1\).
Soit \(d\) un diviseur commun à \(a\) et \(b\) donc \(d\) divise toutes combinaisons linéaires de \(a\) et \(b\), en particulier \(d|au+bv=1\). Ainsi \(|d|=1\). Donc \(a\) et \(b\) sont premiers entre eux.

Réciproquement, si \(a\) et \(b\) sont premiers entre eux, d'après le l'algorithme d'Euclide, on pourra trouver deux entiers \(u,v\) tels que \(au+bv=1\).

Preuve.

Si \(a|bc\) et \(a\) et \(b\) sont premiers entre eux.
Alors, d'après le théorème de Bézout, il existe \(u,v\in\mathbb{Z}\) tels que \(au+bv=1\).
Ainsi, en multipliant par \(c\), on a \(auc+bvc=c\).
Or, \(a|bc\), donc \(a|bvc\). De plus, \(a|auc\). Donc \(a|auc+bvc\), i.e \(\boxed{a|c}\).

Preuve.

1. D'après le théorème de Bézout, il existe \(u,v\in\mathbb{Z}\) tels que \(au+bv=1\).
De plus, il existe \(p,q\in\mathbb{Z}\) tels que \(ap+cq=1\).
En multipliant ces deux relations, on obtient : \((au+bv)(ap+cq) = 1 \times 1\)
\(a(uap + ucq + vbp) + bc(vq) = 1\).
En posant \(u' = uap + ucq + vbp\) et \(v' = vq\), on a \(au' + (bc)v' = 1\).
Ainsi, d'après le théorème de Bézout, \(a\) et \(bc\) sont premiers entre eux, i.e \(\boxed{a\wedge bc=1}\).

2. Comme \(b|a\) alors il existe un entier \(k\) tel que \(a=bk\).
Comme \(c|a\) alors il existe un entier \(k'\) tel que \(a=ck'\).
D'où \(bk=ck'\) i.e \(b|ck'\).
Or, comme \(b\wedge c=1\), alors d'après le théorème de Gauss, \(b|k'\). Donc il existe \(k"\) tel que \(k'=bk"\).
D'où \(a=ck'=cbk"\). Par conséquent, \(\boxed{bc|a}\).

Preuve.

1. Si \(b|a\) alors il existe un entier \(k\) tel que \(a=kb\). Donc le plus grand diviseur commun positif entre \(b\) et \(kb\) est \(|b|\).
Réciproquement, si \(a \wedge b = |b|\), alors \(|b| | a\) ce qui implique que \(b|a\).

2. si \(a\neq 0\), alors comme le plus grand diviseur de \(a\) est \(|a|\) et que \(|a|\) divise 0, on a que \(a \wedge 0 = |a|\).
De plus comme le plus grand diviseur de 1 est 1 et que 1 divise \(a\), on obtient \(a \wedge 1 = 1\).

Preuve.

1.
- Si \(n\) est premier. \(n|n\) donc la propriété est vérifiée.
- Si \(n\) n'est pas premier. Alors \(n\) admet un diviseur \(d\) tel que \(1 < d < n\). Notons \(p\) le plus petit de ces diviseurs. Montrons que \(p\) est premier.
Par l'absurde, si \(p\) n'est pas premier, alors il existe \(p'\) qui divise \(p\) tel que \(1 < p' \leq p\). Alors \(p'|p\) et \(p|n\) donc par transitivté, \(p'|n\). Or \(p' \le p\), et comme \(p\) est le *plus petit* diviseur, on doit avoir \(p'=p\). Ceci contredit \(1 < p' < p\). (Correction: \(1 < p' \le p\). Si \(p' < p\), absurde. Si \(p'=p\), c'est que le seul diviseur est p, ce qui est ok).
*Version simplifiée :* Soit \(p\) le plus petit diviseur de \(n\) tel que \(p > 1\). Si \(p\) n'était pas premier, il aurait un diviseur \(p'\) tel que \(1 < p' < p\). Par transitivité, \(p'|p\) et \(p|n\) implique \(p'|n\). C'est absurde car \(p'\) est un diviseur de \(n\) plus petit que \(p\). Donc \(p\) est premier.

2. Posons \(d=n\wedge p\).
Alors \(d|p\). Comme \(p\) est premier, ses seuls diviseurs positifs sont 1 et \(p\). Donc soit \(d=1\) soit \(d=p\). Si \(d=p\), alors \(p|n\). Si \(d=1\), alors \(n \wedge p = 1\).

3. Par l'absurde supposons qu'il existe un nombre fini de nombres premiers : \({p_1,p_2,...,p_n}\).
Posons \(N=p_1\times p_2\times...\times p_n +1\).
Comme \(N \ge 2\), \(N\) admet au moins un diviseur premier (d'après (i)) qu'on note \(p\).
Comme \(p\) est premier, il figure parmi \({p_1,p_2,...,p_n}\). Donc \(p\) est l'un des \(p_i\).
Donc \(p|p_1\times p_2\times...\times p_n\). Or \(p\) divise \(N\). Ainsi, \(p\) divise leur différence : \(p|(N-p_1\times p_2\times...\times p_n)\), i.e \(p|1\).
Ce qui est absurde car \(p \ge 2\). Donc l'ensemble \(\mathcal{P}\) est infini.

4. Par contraposée, si \(n\) n'est pas premier (et \(n \ge 2\)).
Alors \(n=pq\) avec \(1 < p \le q < n\). Si \(p > \sqrt n\), alors \(q \ge p > \sqrt n\), et \(pq > \sqrt n \times \sqrt n = n\). C'est absurde. Donc on a forcément \(p \le \sqrt n\).
\(n\) admet donc un diviseur \(p\) dans l'intervalle \([\![2;\sqrt n]\!]\). (On peut prendre \(p\) premier en utilisant (i)).

5. Si \(p\) ne divise pas \(n\).
Alors d'après (ii) \(n\wedge p=1\). Comme \(p|nm\), d'après le théorème de Gauss, \(p|m\).

6. On sait que \(k\binom{p}{k}=p\binom{p-1}{k-1}\) pour \(1 \le k \le p\). Donc \(p|k\binom{p}{k}\).
Or, pour \(k\in [\![1;p-1]\!]\), \(p\) est premier et \(k < p\), donc \(k\wedge p=1\).
D'après le théorème de Gauss, comme \(p|k\binom{p}{k}\) et \(p\wedge k = 1\), on a \(p|\binom{p}{k}\).
D'après la formule du binôme de Newton : \((a+b)^p = \sum_{k=0}^{p} \binom{p}{k} a^k b^{p-k}\).
\((a+b)^p = \binom{p}{0}a^0b^p + \sum_{k=1}^{p-1} \binom{p}{k} a^k b^{p-k} + \binom{p}{p}a^pb^0 = b^p + a^p + \sum_{k=1}^{p-1} \binom{p}{k} a^k b^{p-k}\).
Or, d'après ce qu'on vient de montrer, pour \(k\in [\![1;p-1]\!]\), \(p|\binom{p}{k}\), donc \(\binom{p}{k} \equiv 0\ [p]\).
Ainsi \((a+b)^p\equiv a^p+b^p\ [p]\).

Preuve.

Soit \(n\in\mathbb{N}\), on procède par récurrence sur \(n\).
Initialsation : Pour \(n=0\), \(0^p \equiv 0\ [p]\). C'est vrai.
Hérédité : Supposons \(n^p\equiv n\ [p]\) pour un \(n \ge 0\).
Montrons que \((n+1)^p\equiv n+1\ [p]\).
D'après Théorème 11. (vi), \((n+1)^p\equiv n^p+1^p\ [p]\), i.e \((n+1)^p\equiv n^p+1\ [p]\).
Par hypothèse de récurrence, \(n^p\equiv n\ [p]\).
D'où, \((n+1)^p\equiv n+1\ [p]\).
Ce qui achève la récurrence pour \(n \ge 0\). (Le cas \(n < 0\) s'en déduit aussi).

Si \(p\) ne divise pas \(n\).
Comme \(n^p\equiv n\ [p]\), alors \(p|n^p-n\), i.e \(p|n(n^{p-1}-1)\).
Or, comme \(p\) ne divise pas \(n\), et que \(p\) est premier, alors d'après Théorème 11. (ii) \(p\) est premier avec \(n\).
Donc d'après le théorème de Gauss, \(p|n^{p-1}-1\). C'est à dire : \(n^{p-1}\equiv 1 [p]\).

Preuve. (Existence)

On procède par récurrence forte.
Initialisation : Pour \(n=2\) : \(2 = 2^1\). 2 est premier, \(\alpha_1=1\). C'est vrai.
Hérédité : On suppose la propriété vraie pour tous les entiers \(k\) tels que \(2 \le k \le n\).
Regardons \(n+1\).
D'après Théorème 11 (i), \(n+1\) admet au moins un diviseur premier \(p\).
Donc il existe un entier \(k\) tel que \(n+1 = pk\).
- Si \(k=1\) alors \(n+1 = p\). \(n+1\) est premier, la propriété est vraie (\(m=1, p_1=p, \alpha_1=1\)).
- Si \(k > 1\). On a \(p \ge 2\), donc \(k = (n+1)/p \le (n+1)/2 \le n\) (pour \(n \ge 1\)).
Comme \(2 \le k \le n\), on peut appliquer l'hypothèse de récurrence à \(k\).
Donc \(k\) est décomposable en produit de facteurs premiers : \(k = p'_1{}^{\beta_1} \times ... \times p'_r{}^{\beta_r}\).
Par conséquent \(n+1 = p \times k = p \times (p'_1{}^{\beta_1} \times ... \times p'_r{}^{\beta_r})\).
\(n+1\) est aussi décomposable (il suffit de regrouper \(p\) avec les \(p'_i\) s'il est égal à l'un d'eux).
Ce qui achève la récurrence.

Preuve. (Admise, mais l'idée est ci-dessous)

On procède par récurrence forte sur \(n \ge 2\).
Initialisation : Pour \(n=2\), c'est évident car 2 est premier (\(2 = 2^1\)).
Hérédité : Supposons l'unicité vraie pour tous les entiers \(k\) tels que \(2 \le k < n\).
Supposons que \(n\) ait deux décompositions :
\(n=p_1^{\alpha_1}\times...\times p_m^{\alpha_m} = q_1^{\beta_1}\times...\times q_r^{\beta_r}\) (avec \(p_i\) distincts et \(q_j\) distincts).
\(p_1\) divise \(n\), donc \(p_1\) divise \(q_1^{\beta_1}\times...\times q_r^{\beta_r}\).
Comme \(p_1\) est premier, il doit diviser l'un des \(q_j\) (par une généralisation du Thm 11.v).
Comme \(q_j\) est premier, on a forcément \(p_1 = q_j\).
De même, \(q_1\) divise \(n\), donc \(q_1\) doit être égal à l'un des \(p_i\).
En réordonnant, on peut supposer \(p_1 = q_1\).
Posons \(n' = n/p_1\). On a \(n' = p_1^{\alpha_1-1}\times...\times p_m^{\alpha_m} = q_1^{\beta_1-1}\times...\times q_r^{\beta_r}\).
Comme \(p_1 \ge 2\), on a \(n' < n\).
Si \(n'=1\), alors \(n=p_1\) et \(n=q_1\), \(\alpha_1-1=0\), \(\beta_1-1=0\). L'unicité est vraie.
Si \(n' \ge 2\), on applique l'hypothèse de récurrence à \(n'\) : sa décomposition est unique.
Cela force \(m=r\), \(p_i = q_i\) pour tous \(i\), et \(\alpha_i-1 = \beta_i-1\) (sauf pour \(i=1\)) et \(\alpha_1-1 = \beta_1-1\).
Donc \(\alpha_i = \beta_i\) pour tous \(i\).
L'unicité est démontrée.