Soient {m,M,r\in\mathbb{N}}, {r\geq3}, et {k_0,\ldots,k_M\in\mathbb{Z}} tels que {\sum_{i=0}^M k_i r^i=\sum_{i=0}^m r^i.}Montrer que {\sum\limits_{i=0}^M|k_i|\geq m+1}.

Question 1) Montrer que {r_n=O(4^n)}.

Question 2) Montrer que {c_n^{c_n}=O(r_n)}.

Question 3) En déduire {c_n=O(n/\ln n)}.

Question 1) Redémontrer la multiplicativité de l’indicatrice d’Euler {\varphi}, donner sa formule explicite et calculer {\sum\limits_{d\mid n}\varphi(d)}.

Question 2) Exprimer {\varphi(mn)} en fonction de {\varphi(m),\varphi(n),\varphi(m\wedge n)} et {m\wedge n}.

Question 3) Soit {\mu(n)=0} si un carré premier divise {n}, et {\mu(n)=(-1)^{d_n}} sinon, où {d_n} est le nombre de diviseurs premiers distincts de {n}.

Montrer que {\mu} est multiplicative et calculer {\sum\limits_{d\mid n}\mu(d)/d}.

Question 1) Montrer que {\cos(\pi/8)} est irrationnel.

Question 2) Montrer qu’un entier algébrique rationnel est entier.

Question 3) Déterminer les {q\in\mathbb{Q}} tels que {\cos(q\pi)\in\mathbb{Q}}.

Soit {u_0=1}. Pour {n\geq1}, multiplier {u_{n-1}} par {2} si {n\geq2} est une puissance de {2}, le remplacer par {\lceil u_{n-1}/3\rceil} si {n\geq3} est une puissance de {3}, et le laisser inchangé sinon.

Montrer que {u_n\to+\infty}.

Montrer que l’aire d’un polygone entier, de sommets dans {\mathbb{Z}^2}, vaut {i+k/2-1}, où {i} compte ses points entiers intérieurs et {k} ceux du bord.

Si {X,Y} sont indépendantes et uniformes sur {\mathbb{Z}/n\mathbb{Z}}, déterminer {\mathbb{P}(XY=0)}.

Pour {n\ge1}, soit {E(n)} la valuation {5}-adique de {\prod\limits_{k=1}^n k^k}.

Donner un équivalent de {E(n)} quand {n\to+\infty}.

Soit {p>1} premier.

Montrer que {-1} est un carré modulo {p} si et seulement si {p} est somme de deux carrés d’entiers.

Question a) Si {p} est premier impair, montrer que {\mathbb{F}_p^\star} contient {(p-1)/2} carrés.

Question b) Montrer que tout élément de {\mathbb{F}_p} est somme de deux carrés.

Question c) Si {n} est impair, montrer que tout élément de {(\mathbb{Z}/n\mathbb{Z})^\star} est somme de deux carrés.

Question a) Montrer que {v_p(H_{p-1})\ge1} si {p\ge3} est premier.

Question b) Montrer que {v_p(H_{p-1})\ge2} si {p\ge5} est premier.

Question c) Montrer que {v_p(H_{(p-1)p})\ge1} si {p\ge5} est premier.

Pour {H_n=\sum\limits_{k=1}^n1/k}, calculer {v_2(H_n)}, où {v_p(a/b)=v_p(a)-v_p(b)}.

Soient {p,q} deux nombres premiers distincts et {N(m)=\prod\limits_{j=1}^m(1-q^j)}.

Trouver {c>0} tel que {v_p(N(m))\le cm\log m} pour tout {m\ge1}.

Question a) Montrer qu’il existe une infinité de premiers {p\equiv2\pmod3}.

Question b) Écrire {p=3k+2} et supposer {A\subset[-k,k]}.

Montrer que {B\subset A} est sans somme si et seulement si son image modulo {p} l’est.

Question c) Pour {x\in\mathbb{F}_p^\star}, montrer que {B_x=\left\{a\in A:x^{-1}\bar a\in\left\{k+1,\ldots,2k+1\right\}\right\}} est sans somme.

Question d) Conclure.

Pour {f\in\mathbb{Z}[X]}, poser {S_q=\sum_{\substack{0\le a\lt q\\[4pt]\gcd(a,q)=1}} \sum_{n=0}^{q-1}\exp(2\pi i af(n)/q).}Montrer que {S_{qq'}=S_qS_{q'}} si {\gcd(q,q')=1}.

Une partie {X\subset\mathbb{C}} est dite intégrable si toutes les distances entre ses points sont entières.

Montrer que, pour tout {n\in\mathbb{N}}, il existe une telle partie de {n} points sur un même cercle.

Question a) Montrer que {(P(n))} convient pour {P\in\mathbb{Z}[X]}.

Question b) Montrer que {(\lfloor n!e\rfloor)} convient.

Question c) Trouver {P\in\mathbb{Q}[X]\setminus\mathbb{Z}[X]} entier sur {\mathbb{Z}} dont les valeurs ne conviennent pas.

Soient {a,b,m,p\in\mathbb{N}} avec {a^2+b^2-pm=-1} et {A=\begin{pmatrix}p&a+ib\\[4pt]a-ib&m\end{pmatrix}}.

Existe-t-il {B\in\mathrm{GL}_2(\mathbb{Q}(i))} tel que {A=B^\starB} ?

Même question dans {\mathrm{GL}_2(\mathbb{Z}[i])}.

Montrer que les matrices entières {\begin{pmatrix}a&b\\[4pt]c&d\end{pmatrix}} de déterminant {1} avec {a\equiv d\equiv1\pmod3}, {c\equiv0\pmod3}, forment le groupe engendré par {T=\begin{pmatrix}1&1\\[4pt]0&1\end{pmatrix}} et {U=\begin{pmatrix}1&0\\[4pt]3&1\end{pmatrix}}.

Question a) Si un disque fermé {A} a une aire supérieure à ce volume, montrer qu’il contient deux points distincts dont la différence est dans {L}.

Question b) En déduire un {\ell\in L\setminus\left\{0\right\}} avec {\lVert \ell\rVert\le(2+\varepsilon)\sqrt{\operatorname{Vol}(L)/\pi}}.

Question c) Si {p\equiv1\pmod4} est premier, montrer d’abord que {\omega^2\equiv-1\pmod p} a une solution, puis que {p=a^2+b^2}.

Question a) Montrer que {P_n(X)=\sum\limits_\sigma X^{I(\sigma)} =\prod\limits_{k=1}^{n-1}(1+X+\cdots+X^k)}.

Question b) Exprimer {f(n)=\#\left\{\sigma:(n+1)\mid I(\sigma)\right\}} à l’aide de {P_n}.

Question c) Montrer qu’il existe une infinité de premiers {p} pour lesquels {f(p-1)\lt (p-1)!/p}, et une infinité pour lesquels l’inégalité est inversée.

On étend naturellement la valuation {2}-adique {v_2} à {\mathbb{Q}^\star}. Pour {n\ge1}, soit {H_n=\sum\limits_{k=1}^n1/k}.

Calculer {v_2(H_n)}.

Question 1) Montrer {\binom{np}m\equiv0\pmod p}.

Question 2) Montrer {\binom{np}{mp}=\sum\limits_{k=0}^p\binom{p(n-1)}{mp-k}\binom pk}.

Question 3) Montrer {\binom{np}{mp}\equiv\binom nm\pmod{p^2}}.

Question 4) Montrer {\binom{p-1}{k-1}\equiv\pm1\pmod p} pour {1\le k\le p}.

Question 5) Montrer {\sum\limits_{k=1}^{p-1}((p-1)!/k)^2\equiv0\pmod p}.

Question 6) En déduire {\binom{2p}p\equiv2\pmod{p^3}}.

Question 1) Déterminer le cardinal des carrés non nuls de {\mathbb{Z}/p\mathbb{Z}}.

Question 2) Montrer {a^{(p-1)/2}\equiv1\pmod p} si et seulement si {a} est un carré non nul modulo {p}.

Question 3) Pour {a=\prod\limits_{k=1}^{(p-1)/2}(2k)}, montrer {a\equiv(-1)^{(p-1)/4}((p-1)/2)!\pmod p} si {p\equiv1\pmod4}, et {a\equiv(-1)^{(p+1)/4}((p-1)/2)!\pmod p} si {p\equiv-1\pmod4}.

Question 1) Résoudre dans le cas {a=b=c}.

Question 2) Traiter le cas {b} impair.

Question 3) Traiter le cas {c} impair.

Question 4) Traiter le cas général.

Question 1) Donner le cardinal de {(\mathbb{Z}/p\mathbb{Z})^\star}.

Question 2) Montrer que {x^2=1} a exactement deux solutions et en déduire le nombre de carrés dans {\mathbb{Z}/p\mathbb{Z}}.

Question 3) Soit {\chi(n)} égal à zéro si {p\mid n}, à un si {n} est un carré non nul modulo {p}, à {-1} sinon.

Montrer {\chi(ab)=\chi(a)\chi(b)}.

Question 4) Calculer {\sum\limits_{k=0}^{p-1}\chi(k)} et majorer {|\sum\limits_{k=0}^N\chi(k)|}.

Question 5) Avec {\xi=e^{2i\pi/p}}, montrer {\chi(n)=\frac1p\sum\limits_{k=0}^{p-1}\sum\limits_{a=0}^{p-1}\chi(a)\xi^{k(a-n)}}.

Question 6) Pour {1\le k\lt p}, poser {S_k(N)=\sum\limits_{n=0}^N\xi^{-kn}}.

Montrer {|S_k(N)|\le1/|\sin(k\pi/p)|}, puis {|S_k(N)|\le p/(2k)} si {k\lt p/2}, et donner une borne similaire si {k>p/2}.

Question 7) Pour {G_k=\sum\limits_{a=0}^{p-1}\chi(a)\xi^{ka}}, montrer {|G_k|=\sqrt p}.

Déterminer les matrices {A\in GL_n(\mathbb{R})} telles que, pour tout entier {k\ge2}, il existe {M\in M_n(\mathbb{Z})} avec {A=M^k}.

Soit {u_0=4}, {u_1=u_2=0}, {u_3=3} et {u_{n+4}=u_n+u_{n+1}} pour tout {n\in\mathbb{N}}.

Montrer que tout nombre premier {p} divise {u_p}.

Question a) Exprimer {F_n} en fonction de {n}.

Question b) Montrer {F_{p+q}=F_pF_{q+1}+F_{p-1}F_q} pour {(p,q)\in\mathbb{N}^\star\times\mathbb{N}}.

Question c) Calculer {F_m\wedge F_n} pour {m,n\ge0}.

On note {d_n} le nombre de diviseurs de {n\in\mathbb{N}^\star}.

Montrer {d_n=O(n^\varepsilon)} pour tout {\varepsilon>0}.

Question a) Montrer qu’il existe une infinité de nombres premiers congrus à {3} modulo {4}.

Question b) Soient {p} premier, {n\ge2} et {k=((np)^p-1)/(np-1)}.

i) Montrer {k\equiv1\pmod p}.

ii) Montrer que tout diviseur positif {d} de {k} vérifie {d\equiv1\pmod p}.

Question c) Montrer qu’il existe une infinité de nombres premiers congrus à {1} modulo tout nombre premier {p}.

Question a) Montrer que chaque {n\in\mathbb{N}} possède une unique suite presque nulle {(a_{k,r}(n))_{k\ge0}} telle que {n=\sum\limits_{k\ge0}a_{k,r}(n)r^k} et {a_{k,r}(n)\in[[0,r-1]]}.

Question b) Pour {k} fixé, montrer que {(a_{k,r}(n))_{n\ge1}} est périodique et trouver sa période.

Question c) Montrer que {(a_{k,r}(n^n))_{n\ge1}} est périodique à partir d’un certain rang.

Question a) Montrer que {\Sigma_2(A)} est stable par multiplication.

Question b) Est-ce toujours le cas de {\Sigma_3(A)} ?

Question c) Supposons que {A} soit un corps de caractéristique différente de {2} et que {n} soit une puissance de {2}.

Pour {c_1,\ldots,c_n\in A}, {s=\sum\limits c_k^2}, construire {M\in M_n(A)} de première ligne {(c_1,\ldots,c_n)} telle que {MM^T=M^TM=sI_n}.

Question d) En déduire que {\Sigma_{2^n}(A)} est stable par multiplication.

Soient {f,g\in\mathbb{Q}[X]} tels que {f(\mathbb{Q})=g(\mathbb{Q})}.

Montrer que {\deg f=\deg g}.

Question a) Montrer que {(H_n)_{n\ge0}} est une base de {\mathbb{C}[X]}.

Question b) Montrer {H_n\in I}.

Question c) Montrer {\Delta H_n=H_{n-1}} pour {n\ge1}.

Question d) Montrer {I\subset\mathbb{Q}[X]}.

Question e) Montrer {I=\left\{\sum\limits_{i=0}^na_iH_i:n\in\mathbb{N},\ (a_0,\ldots,a_n)\in\mathbb{Z}^{n+1}\right\}}.

Question f) Si {P_1,P_2\in I} et {P_1(n),P_2(n)} sont premiers entre eux pour tout entier {n}, montrer qu’il existe {U_1,U_2\in I} avec {U_1P_1+U_2P_2=1}.

Montrer qu’il n’existe aucun triangle rectangle dont les longueurs des côtés appartiennent à {\mathbb{N}^\star} et dont l’aire est un carré parfait non nul.

a)

i) Si {d,d'} sont premiers entre eux, montrer que {A_d\cap A_{d'}=A_{dd'}} et en déduire leur indépendance.

ii) Poser {B=\left\{k\in\Omega:\gcd(k,n)=1\right\}}.

Exprimer {B} en fonction des {A_{p_i}}, puis calculer {P(B)} et {|B|}, cette dernière valeur étant notée {\varphi(n)}.

iii) Pour {m,n} premiers entre eux, montrer {\varphi(mn)=\varphi(m)\varphi(n)}.

b) On note {U=\bigcup_{n\in\mathbb{N}}U_n}, où {U_n} est l’ensemble des racines {n}-ièmes de l’unité, et {n_z=\inf\left\{n\in\mathbb{N}:z\in U_n\right\}} pour {z\in U}.

i) Montrer que tout complexe de module {1} est limite d’une suite d’éléments de {U}.

ii) Pour {m} entier naturel, poser {P_m=\left\{z\in U:n_z=m\right\}}.

Montrer que {|P_m|=\varphi(m)} et que {P_m\cap P_n=\varnothing} si {m\ne n}.

iii) Montrer que {U=\bigcup_{m\in\mathbb{N}}P_m}.