1) Montrer qu’un groupe de cardinal {n} est cyclique si et seulement s’il contient un élément d’ordre {n}.

2) Programmer le pgcd de deux entiers, puis le nombre de générateurs de {(\mathbb{Z}/p\mathbb{Z})^\times}, pour {p} premier.

3) Déterminer {|(\mathbb{Z}/p^\alpha\mathbb{Z})^\times|}.

4) Pour {p} premier, démontrer par récurrence que {(p+1)^{p^k}\equiv1+p^{k+1}\pmod {p^{k+2}}}.

1) Montrer qu’il suffit de tester {0\leq a\lt n}.

Programmer ce test et déterminer le plus petit nombre de Carmichael.

2) Si {n=\prod\limits_{i=1}^k p_i}, {k\geq2}, avec les {p_i} distincts et {p_i-1\mid n-1}, montrer que {a^n\equiv a\pmod {p_i}}, puis que {n} est de Carmichael.

3) Montrer qu’un nombre de Carmichael est sans facteur carré.

4) Dans un groupe abélien fini, montrer que le produit de deux éléments d’ordres premiers entre eux {r,s} est d’ordre {rs}.

Montrer que tout ordre divise l’ordre maximal d’un élément.

1) Programmer {<code>determiner(n)</code>=(p_n,q_n)}.

2) Pour les nombres premiers {n\leq100}, afficher {p_n\bmod n^2} et conjecturer un résultat.

3) Pour {p\geq5} premier, poser {Q(X)=\prod\limits_{k=1}^{p-1}(X+k)=\sum\limits_{k=0}^{p-1}a_kX^k}.

Donner {a_0,a_{p-1}}, établir {(p-1)!\equiv-1\pmod p} et {a_1/(p-1)!=H_{p-1}}.

Poser {V=(i^j)_{1\leq i,j\leq p-1}} et {A=(a_1,\ldots,a_{p-1})^T}.

Montrer qu’il existe un vecteur entier {B} tel que {V(A)=pB}, puis que tous les coefficients de {A} sont multiples de {p}.

4) Démontrer la conjecture.

1) Programmer cette fraction et montrer que {x_n=[1,2,\ldots,2]} ({n} copies de {2}) tend vers {\sqrt2}.

Trouver le premier rang d’erreur au plus {10^{-10}}.

2) Poser {M(a)=\left(\begin{smallmatrix}a&1\\[4pt]1&0\end{smallmatrix} \right)} et {(p_n,q_n)^T=M(a_0)\cdots M(a_n)(1,0)^T}.

Montrer {p_n/q_n=[a_0,\ldots,a_n]}, programmer ces entiers et montrer qu’ils sont premiers entre eux.

3) Pour {x>0}, poser {y_0=x}, {a_n=\lfloor y_n\rfloor}, {y_{n+1}=1/(y_n-a_n)} tant que possible, {x_n=[a_0,\ldots,a_n]}.

Montrer {x_{n+1}-x_n=(-1)^n/(q_nq_{n+1})} et {|x-x_n|\leq1/(q_nq_{n+1})}.

Montrer que l’algorithme s’arrête exactement pour les rationnels.

Démontrer la formule du crible de Poincaré.

Pour {\mu(n)=0} si {n} possède un facteur carré non trivial, {\mu(n)=(-1)^k} si {n} est produit de {k} premiers distincts, exprimer à l’aide de {\mu} la probabilité que deux entiers uniformes indépendants de {\left\{1,\ldots,n\right\}} soient premiers entre eux.

1) Montrer que {C_n\in\mathbb{N}^\star}.

2) Calculer {\sum\limits_{k=0}^nC_kC_{n-k}}.

3) Déterminer les entiers {n} pour lesquels {C_n} est pair, puis impair.

1) Montrer que, pour {n\geq2}, {\frac{4^n}{2\sqrt n}\lt \binom{2n}{n}\lt 4^n}.

2) Montrer que, pour {n\geq1}, {\binom{2n+1}{n}\lt 4^n}.

3) Montrer que, pour {n\in\mathbb{N}}, {P_{2n+1}\lt 4^nP_{n+1}}.

1) Rappeler le petit théorème de Fermat et montrer que {-1\notin C}.

2) Déterminer {|C|}.

3) Pour {x\in C\setminus\left\{0\right\}}, on pose {\pi_x=\prod\limits_{y\in C\setminus\left\{x\right\}}(x+y)}.

Montrer que {\pi_x=\pi_1}.

4) Calculer {\pi=\prod\limits_{x\ne y\in C}(x+y)}.

1) Montrer que, si {M_n} est premier, {n} est premier.

2) Montrer que {s_{n+1}=s_n^2-2}.

Qu’en déduire sur {(s_n)} ?

3) Pour {q} premier, munir {B=(\mathbb{Z}/q\mathbb{Z})^2} des lois {(x,y)+(x',y')=(x+x',y+y'),\qquad (x,y)(x',y')=(xx'+3yy',xy'+x'y).}Montrer que c’est un anneau commutatif fini, qui est un corps si {3} n’est pas un carré modulo {q}.

Montrer que {a+b\sqrt3\mapsto(\bar a,\bar b)} est un morphisme surjectif {\mathbb{Z}+\sqrt3\mathbb{Z}\to B}.

4) Pour {n} premier, montrer que {M_n\mid s_{n-2}} entraîne que {M_n} est premier. On pourra considérer son plus petit facteur premier {q} et l’ordre de {(2,1)} dans {B^\star}.

1) Définir l’indicatrice d’Euler et exprimer {\varphi(n)} avec les facteurs premiers.

2) Calculer {\sum\limits_{d\mid n}\varphi(d)} pour {n\geq2}.

3) En déduire le déterminant de {A=(\gcd(i,j))_{1\leq i,j\leq n}}.

1) Montrer que chaque ligne contient {d} coefficients égaux à un.

2) Avec {U=(1,\ldots,1)^T}, montrer que {AU=dU}, puis {n=d^2+1}.

3) Montrer que {d} est valeur propre simple.

4) Montrer que les autres valeurs propres sont les racines {r_1,r_2} de {X^2+X-d+1}.

5) Établir {m_1+m_2=n-1} et {d+m_1r_1+m_2r_2=0} pour leurs multiplicités.

6) Montrer que {m_1=m_2} entraîne {d=2}. On suppose ensuite {d>2}.

7) Montrer que {4d-3=(2k+1)^2} pour un entier {k}, et {k^4\equiv1\pmod{2k+1}}.

8) Montrer que {16k^4\equiv1\pmod{2k+1}} ; en déduire {d\in\left\{2,3,7,57\right\}}.

1) L’expliciter pour deux puis trois ensembles, et la démontrer pour deux.

2) Poser {\mu(1)=1}, {\mu(n)=(-1)^k} si {n} est produit de {k} nombres premiers distincts, et {\mu(n)=0} sinon.

Exprimer avec {\mu} la probabilité que deux entiers choisis uniformément et indépendamment dans {\left\{1,\ldots,n\right\}} soient premiers entre eux.

a) Montrer qu’un FP est impair.

b) Si {n=\prod\limits_{i=1}^rp_i}, {r\ge2}, avec les {p_i} premiers impairs distincts et {p_i-1\mid n-1}, montrer que {n} est FP.

c) En admettant que {(\mathbb{Z}/p^v\mathbb{Z})^\times} est cyclique pour tout premier impair {p} et tout {v\ge1}, prouver la réciproque.

a) Définir la comatrice et montrer {GL_n(\mathbb{Z})=\left\{M\in M_n(\mathbb{Z}):\det M=\pm1\right\}}.

b) Si {M^k=I} pour un {k\ge1} et {(M-I)/p\in M_n(\mathbb{Z})}, montrer {M=I}.

c) Donner un majorant des cardinaux des sous-groupes finis de {GL_n(\mathbb{Z})}.

a) Montrer que les inversibles de {M_n(\mathbb{Z})} sont exactement les matrices de déterminant {\pm1}.

b) Pour {T_a=\begin{pmatrix}1&a\\[4pt]0&1\end{pmatrix}}, {S_a=\begin{pmatrix}1&a\\[4pt]0&-1\end{pmatrix}}, calculer {T_bS_aT_b^{-1}}.

c) Si {M\in M_2(\mathbb{Z})} vérifie {M^2=I}, montrer qu’il existe {P\in GL_2(\mathbb{Z})} tel que {PMP^{-1}\in\left\{S_0,S_1\right\}}.

d) {S_0,S_1} sont-elles conjuguées dans {GL_2(\mathbb{Z})} ?

a) Montrer leur multiplicativité sur les entiers premiers entre eux.

b) Donner une expression simple de {\Lambda(n)}.

c) Pour {|z|\lt 1}, montrer {\sum\limits_{n\ge1}\lambda(n)z^n/(1-z^n)=\sum\limits_{n\ge1}z^{n^2}}.