Nombres premiers entre eux

Bonjour,

Pour tout $n$ entier, $1\wedge n=1$, non ?

Bonjour,
ce n'est pas un exercice facile (il a été posé à l'oral de l'ENS Lyon l'année dernière).
Pour commencer : si on suppose l'ensemble considéré comme étant infini, que peut-on dire de $\text{PGCD}(a,b,c,d)$ et de $ad-bc$ ?
A partir de là, on peut trouver une condition nécessaire (c'est la partie la plus simple).
Il faut ensuite montrer qu'elle est suffisante (c'est la partie un peu plus délicate).
Bon travail !
LP

supp

supp

@Side : on arrive à une CNS assez simple du type : (condition 1) et (condition 2 ou condition 3).

Tu as raison sur les deux points.
Je ne voulais pas vendre la mèche trop vite dans mon indication...

Le message de reuns n'est pas lisible à cause de la formule qui déborde.
Comme je l'écrivais plus haut, on peut se ramener au cas $c=0$ en échelonnant la matrice $A=\pmatrix{a&b\\ c& d}$. Supposons $a$ et $c$ non tous les deux nuls, soit $g=\mathrm{pgcd}(a,c)\neq 0$ et $g=ua+vc$ une identité de Bézout. On pose $a'=a/g$, $c'=c/g$. La matrice $U=\pmatrix{u&v\\-c'&a'}$ est de déterminant $1$, donc inversible sur $\mathbb Z$. On a $UA=\pmatrix{g&e\\0&f}$ avec $e$ et $f$ des entiers que je n'explicite pas.

Le vecteur $A\pmatrix {n\\1}\in \mathbb Z^2$ est primitif (ses coefficients sont premiers entre eux) si et seulement si $UA\pmatrix {n\\1}$ est primitif.
Par ailleurs l'idéal engendré par les coefficients de $A$ est le même que celui engendré par les coefficients de $UA$, donc les pgcd des coefficients de ces deux matrices sont égaux. Enfin les déterminants de $A$ et $UA$ sont aussi égaux.

Si $\mathrm{pgcd}(e,f,g)\neq 1$, alors $UA\pmatrix {n\\1}$ n'est primitif pour aucun entier $n$.
Supposons $\mathrm{pgcd}(e,f,g)= 1$.
Si $f=0$ (ce qui équivaut à $\det(UA)=0$ puisque $g\neq 0$), alors $UA\pmatrix {n\\1}$ n'est primitif que si $gn+e=\pm1$, et ça ne peut arriver que pour un nombre fini de $n$.

Si $f\neq 0$, soit $\mathcal D$ l'ensemble fini des diviseurs premiers de $f$ et soit $D$ le produit de $\mathcal D$. Pour tout $p\in \mathcal D$, il existe un entier $\ell_p$ tel que $g\ell_p+e\neq 0\pmod p$ puisque $p$ ne divise pas à la fois $g$ et $e$. Le théorème chinois nous dit qu'il existe un entier $\ell$ congru à $\ell_p$ pour tout $p\in \mathcal D$. Alors, pour tout entier $k$, le vecteur $UA\pmatrix{\ell+kD\\1}$ est primitif.

Il reste à traiter le cas ou $a=c=0$. Facile !