Exercices de PGCD et nombres premiers, Terminale (page 3)

Déterminer le PGCD de $2024$ et $341$ en rédigeant intégralement l'algorithme d'Euclide, puis indiquer combien de divisions ont été nécessaires.

Déterminer un couple d'entiers $(u,v)$ tel que $161u+128v=1$.

Démontrer que, pour tout entier naturel $n$, les entiers $7n+4$ et $5n+3$ sont premiers entre eux.

Soit $n$ un entier relatif. Démontrer que si $7$ divise $3n^2$, alors $7$ divise $n$.

Décomposer $180$ et $378$ en produits de facteurs premiers, puis en déduire leur PGCD et leur PPCM.

Résoudre dans ${\mathbb{Z}}^2$ l'équation $5x+3y=32$. Donner ensuite les solutions appartenant à ${\mathbb{N}}^2$.

(

Dresser la liste des nombres premiers compris entre $180$ et $230$, en explicitant le principe du crible d'Ératosthène et la borne des éliminations.

Résoudre dans ${\mathbb{Z}}^2$ l'équation $6x-5y=13$.

Résoudre dans ${\mathbb{Z}}^2$ l'équation $24x+36y=60$.

Un laboratoire code chaque échantillon par un numéro à six chiffres $abcdef$, complété d'une clé $K$ définie par $K\equiv 3a+5b+7c+11d+13e+17f[26]$, avec $0⩽K⩽25$. Un échantillon porte le numéro $12c456$, où le troisième chiffre $c$ est illisible, ainsi que la clé $K=20$.
(

On chiffre un message en numérotant les lettres de A à Z par $0$ à $25$, puis en remplaçant chaque nombre $x$ par le nombre $y$ vérifiant $y\equiv 7x+11[26]$.
(

Déterminer le reste de la division euclidienne de $7^{325}$ par $11$.

Pour tout entier naturel $n$, on pose $F_n=2^{2^n}+1$.
(1) Vérifier que $F_0=3$, $F_1=5$ et $F_2=17$, et que ces trois nombres sont premiers.
(2) Étudier la primalité de $F_3=257$.
(3) Fermat a conjecturé que tous les nombres $F_n$ sont premiers. On admet que $F_5=2^{32}+1=4294967297=641\times 6700417$. Cette conjecture est-elle fondée ?

On admet la formule $1^2+2^2+\dots +n^2=\frac{n(n+1)(2n+1)}{6}$ pour tout entier $n⩾1$. Démontrer que cette somme est un entier, c'est-à-dire que $6$ divise $n(n+1)(2n+1)$ pour tout entier $n⩾1$.

Un carillon sonne toutes les $7$ heures, la première fois $3$ heures après minuit ; un second carillon sonne toutes les $13$ heures, la première fois $2$ heures après minuit. Déterminer toutes les heures, comptées après minuit, auxquelles les deux carillons sonnent ensemble, puis la première d'entre elles.

Soit $P$ le polynôme défini par $P(x)=6x^3+x^2-19x+6$.
(1) Montrer que si $\frac{p}{q}$ est une racine rationnelle de $P$, écrite sous forme irréductible avec $q>0$, alors $p$ divise $6$ et $q$ divise $6$.
(2) Lister tous les candidats, puis déterminer toutes les racines rationnelles de $P$.

(1) Soit $p$ un nombre premier et $a$ un entier non divisible par $p$. Montrer que $a^{p-2}$ est un inverse de $a$ modulo $p$.
(2) En déduire l'inverse de $7$ modulo $13$, puis contrôler le résultat.

(1) Soient $a$ et $b$ deux entiers non nuls et $k$ un entier relatif. Démontrer que $\mathrm{PGCD}(a,b)=\mathrm{PGCD}(a,b-ka)$.
(2) Application : déterminer, pour tout entier naturel $n$, le PGCD de $5n+3$ et $3n+2$.

Soit $n$ un entier, $n⩾2$. On note $n!$ le produit $1\times 2\times \dots \times n$.
(

On numérote les lettres de A à Z par $0$ à $25$ et on découpe les messages en paires de lettres. Chaque paire, vue comme un couple de nombres, est chiffrée par la matrice $M=\left(\begin{array}{cc}2& 3\\ 1& 4\end{array}\right)$, les résultats étant pris modulo $26$.
(

Dans un mini-système RSA, on choisit les nombres premiers $p=5$ et $q=17$.
(1) Calculer $n=pq$ et $\phi =(p-1)(q-1)$.
(2) Vérifier que la clé publique $e=7$ convient, puis déterminer la clé privée $d$, inverse de $e$ modulo $\phi$.
(3) Chiffrer le message $m=3$, puis montrer, à l'aide du petit théorème de Fermat, que le déchiffrement redonne bien $3$.

Un club doit acheter des dossards à $23$ euros pièce et des maillots à $17$ euros pièce, pour une dépense exactement égale à $1500$ euros. Déterminer toutes les compositions possibles de l'achat (nombres entiers de dossards et de maillots, éventuellement nuls).

Pour tout entier naturel $n$, on pose $a_n=4^n+3$.
(1) Montrer que pour tout $n$, le nombre $a_n$ n'est pas divisible par $3$.
(2) En déduire que deux termes consécutifs $a_n$ et $a_{n+1}$ sont toujours premiers entre eux.
(3) Calculer $a_1$, $a_2$, $a_3$ et $a_4$, puis étudier leur primalité. La suite ne fournit-elle que des nombres premiers ?

Un triangle rectangle est dit pythagoricien lorsque ses trois côtés ont des longueurs entières, et primitif lorsque ces longueurs n'ont pas de diviseur commun supérieur à $1$. On cherche tous les triangles pythagoriciens d'hypoténuse $65$.
(1) Vérifier que les triangles de côtés $(16,63,65)$ et $(33,56,65)$ sont pythagoriciens.
(2) Montrer qu'un triangle pythagoricien non primitif d'hypoténuse $65$ est un multiple entier d'un triangle primitif d'hypoténuse $5$ ou $13$, et exhiber les deux triangles obtenus ainsi.
(3) On admet que dans un triangle pythagoricien primitif d'hypoténuse impaire $z$, les côtés de l'angle droit s'écrivent $x=st$ et $y=\frac{t^2-s^2}{2}$ avec $z=\frac{s^2+t^2}{2}$, où $s$ et $t$ sont deux entiers impairs premiers entre eux, $s<t$. Déterminer les triangles primitifs d'hypoténuse $65$.
(4) Conclure en donnant la liste complète des triangles pythagoriciens d'hypoténuse $65$.

On s'intéresse à l'équation de Pell-Fermat $x^2-2y^2=1$, d'inconnues $x$ et $y$ entières.
(