QCM Bilan : PGCD et nombres premiers

[enonce]
Ce QCM bilan couvre l'ensemble du chapitre : PGCD, identités de Bézout, théorème de Gauss et nombres premiers. Choisissez la bonne réponse parmi les quatre propositions.
[/enonce]

[etape]
On donne $a = 2^{4} \times 3^{2} \times 5$ et $b = 2^{2} \times 3^{3} \times 7$. Quel est le PGCD de $a$ et $b$ ?
[qcm]
[option]$2^{4} \times 3^{3}$[/option]
[option correct="true"]$2^{2} \times 3^{2}$[/option]
[option]$2^{4} \times 3^{3} \times 5 \times 7$[/option]
[option]$2 \times 3$[/option]
[reponse statut="correct"]Bonne réponse !
Pour le PGCD à partir des décompositions, on garde chaque facteur premier commun avec le plus petit exposant. Pour $2$ : $\min(4\,;\,2) = 2$. Pour $3$ : $\min(2\,;\,3) = 2$. $5$ et $7$ ne sont pas communs. Donc $\text{PGCD}(a\,;\,b) = 2^{2} \times 3^{2} = 36$.[/reponse]
[reponse motif="$2^{4} \times 3^{3}$"]Non.
On a pris l'exposant maximum au lieu du minimum. La règle pour le PGCD est exactement l'inverse : minimum à chaque facteur commun.[/reponse]
[reponse motif="$2^{4} \times 3^{3} \times 5 \times 7$"]Non.
Cette expression est en réalité le PPCM (plus petit multiple commun) : on prend tous les facteurs avec l'exposant maximum. Le PGCD ne garde que les facteurs communs et avec le minimum.[/reponse]
[reponse motif="$2 \times 3$"]Non.
$6$ divise bien $a$ et $b$, mais ce n'est pas le plus grand diviseur commun. Reprendre : $\min(4\,;\,2) = 2$, $\min(2\,;\,3) = 2$.[/reponse]
[reponse statut="incorrect"]Non.
Pour le PGCD, on prend chaque facteur premier commun avec son exposant minimum : $2^{\min(4,2)} \times 3^{\min(2,3)} = 2^{2} \times 3^{2} = 36$.[/reponse]
[/qcm]
[/etape]

[etape]
Parmi les équations suivantes dans $\mathbb{Z}^2$, laquelle n'admet aucune solution ?
[qcm]
[option]$6x + 9y = 30$[/option]
[option correct="true"]$4x + 6y = 7$[/option]
[option]$5x + 7y = 100$[/option]
[option]$8x + 12y = 16$[/option]
[reponse statut="correct"]Bonne réponse !
Une équation $ax + by = c$ admet des solutions entières si et seulement si $\text{PGCD}(a\,;\,b)$ divise $c$. Ici $\text{PGCD}(4\,;\,6) = 2$, et $2$ ne divise pas $7$. Donc aucun couple $(x\,;\,y) \in \mathbb{Z}^2$ ne convient.[/reponse]
[reponse motif="$6x + 9y = 30$"]Non.
$\text{PGCD}(6\,;\,9) = 3$ et $3 \mid 30$, donc l'équation admet des solutions (par exemple $x = 2$, $y = 2$ : $12 + 18 = 30$).[/reponse]
[reponse motif="$5x + 7y = 100$"]Non.
$\text{PGCD}(5\,;\,7) = 1$ : $5$ et $7$ sont premiers entre eux, donc $1$ divise n'importe quel entier. L'équation admet des solutions quel que soit le second membre.[/reponse]
[reponse motif="$8x + 12y = 16$"]Non.
$\text{PGCD}(8\,;\,12) = 4$ et $4 \mid 16$, donc l'équation admet des solutions (par exemple $x = 2$, $y = 0$).[/reponse]
[reponse statut="incorrect"]Non.
Le critère est : $ax + by = c$ a des solutions dans $\mathbb{Z}^2$ ssi $\text{PGCD}(a\,;\,b)$ divise $c$. Vérifie chaque équation et trouve celle où ce n'est pas le cas.[/reponse]
[/qcm]
[/etape]

[etape]
Soit $n$ un entier naturel. Que vaut $\text{PGCD}(n\,;\,n^{2} + 1)$ ?
[qcm]
[option]$n$[/option]
[option correct="true"]$1$[/option]
[option]$n^{2}$[/option]
[option]$n + 1$[/option]
[reponse statut="correct"]Tu as raison !
Soit $d$ ce PGCD : $d \mid n$ donc $d \mid n^{2}$, et $d \mid n^{2} + 1$ par hypothèse. Donc $d$ divise leur différence $1$. Conclusion : $d = 1$.[/reponse]
[reponse motif="$n$"]Non.
Si $n$ divisait $n^{2} + 1$, alors $n$ diviserait $1$, donc $n = 1$. La conclusion ne peut donc pas être valable pour tout $n$.[/reponse]
[reponse motif="$n^{2}$"]Non.
Un PGCD ne peut pas dépasser le plus petit des deux nombres. Or $n^{2}$ est en général plus grand que $n$.[/reponse]
[reponse motif="$n + 1$"]Non.
Aucun lien direct n'apparaît entre $n + 1$ et le PGCD demandé. Tester avec $n = 2$ : $\text{PGCD}(2\,;\,5) = 1$, alors que $n + 1 = 3$.[/reponse]
[reponse statut="incorrect"]Non.
Tout diviseur commun $d$ doit aussi diviser $(n^{2} + 1) - n \times n = 1$. Donc $d = 1$ : $n$ et $n^{2} + 1$ sont premiers entre eux.[/reponse]
[/qcm]
[/etape]

[etape]
Soient $n = 2^{3} \times 3^{2} \times 5 \times 11$ et $m = 2^{2} \times 5^{2} \times 13$. Quels facteurs premiers apparaissent dans $\text{PGCD}(n\,;\,m)$ ?
[qcm]
[option]$2$, $3$, $5$, $11$ et $13$.[/option]
[option correct="true"]$2$ et $5$ uniquement.[/option]
[option]$3$ et $11$ uniquement.[/option]
[option]Aucun (PGCD = $1$).[/option]
[reponse statut="correct"]Bravo !
Seuls les facteurs premiers présents dans les deux décompositions interviennent dans le PGCD : $2$ apparaît dans $n$ et $m$, $5$ aussi. $3$, $11$ et $13$ n'apparaissent que dans l'un des deux nombres.[/reponse]
[reponse motif="$2$, $3$, $5$, $11$ et $13$."]Non.
Cette liste est celle du PPCM (réunion des facteurs premiers). Le PGCD ne retient que les facteurs communs.[/reponse]
[reponse motif="$3$ et $11$ uniquement."]Non.
$3$ et $11$ apparaissent uniquement dans $n$, pas dans $m$. Ils ne peuvent pas figurer dans le PGCD.[/reponse]
[reponse motif="Aucun (PGCD = $1$)."]Non.
$2$ et $5$ apparaissent dans les deux décompositions, donc le PGCD est différent de $1$. En l'occurrence $\text{PGCD}(n\,;\,m) = 2^{2} \times 5 = 20$.[/reponse]
[reponse statut="incorrect"]Non.
Le PGCD ne contient que les facteurs premiers présents dans les deux décompositions. Ici, $n$ et $m$ partagent $2$ et $5$, mais pas $3$, $11$ ou $13$.[/reponse]
[/qcm]
[/etape]

[etape]
On sait que $\text{PGCD}(a\,;\,b) = 1$ et que $a$ divise $bc$. Que peut-on en conclure ?
[qcm]
[option]$a$ divise $b$.[/option]
[option]$c$ divise $a$.[/option]
[option correct="true"]$a$ divise $c$.[/option]
[option]$a$ divise $b - c$.[/option]
[reponse statut="correct"]Parfait !
C'est exactement l'énoncé du théorème de Gauss : $a \mid bc$ et $\text{PGCD}(a\,;\,b) = 1$ entraînent $a \mid c$.[/reponse]
[reponse motif="$a$ divise $b$."]Non.
Au contraire, l'hypothèse $\text{PGCD}(a\,;\,b) = 1$ exclut quasiment la divisibilité de $b$ par $a$ (sauf si $a = 1$). C'est l'autre facteur, $c$, qui est concerné.[/reponse]
[reponse motif="$c$ divise $a$."]Non.
Le théorème de Gauss conclut bien à une divisibilité, mais c'est $a \mid c$ (pas l'inverse). Inverser le sens de la divisibilité change complètement le résultat.[/reponse]
[reponse motif="$a$ divise $b - c$."]Non.
Aucune information n'est apportée sur $b - c$ par les hypothèses. La conclusion correcte porte uniquement sur $c$.[/reponse]
[reponse statut="incorrect"]Non.
Théorème de Gauss : si $a \mid bc$ et $\text{PGCD}(a\,;\,b) = 1$, alors $a \mid c$.[/reponse]
[/qcm]
[/etape]

[etape]
Combien le nombre $N = 2^{4} \times 3 \times 7^{2}$ admet-il de diviseurs positifs ?
[qcm]
[option]$8$[/option]
[option]$15$[/option]
[option correct="true"]$30$[/option]
[option]$N$ lui-même.[/option]
[reponse statut="correct"]C'est bien ça !
$(4+1) \times (1+1) \times (2+1) = 5 \times 2 \times 3 = 30$ diviseurs : on multiplie les $a_{i} + 1$ pour chaque facteur premier de la décomposition.[/reponse]
[reponse motif="$8$"]Non.
On a peut-être ajouté les exposants au lieu de les multiplier : $4 + 1 + 2 = 7$ ou similaire. La règle est multiplicative : $(4+1) \times (1+1) \times (2+1)$.[/reponse]
[reponse motif="$15$"]Non.
On a peut-être omis l'un des facteurs $(a_{i} + 1)$, par exemple en oubliant le facteur $3$. Reprendre : $5 \times 2 \times 3 = 30$.[/reponse]
[reponse motif="$N$ lui-même."]Non.
$N$ est l'entier dont on cherche les diviseurs ; il a beaucoup moins de $N$ diviseurs (heureusement !). $30$ diviseurs ici.[/reponse]
[reponse statut="incorrect"]Non.
Pour $N = p_{1}^{a_{1}} \cdots p_{k}^{a_{k}}$, le nombre de diviseurs vaut $(a_{1}+1) \times (a_{2}+1) \times \cdots \times (a_{k}+1)$. Ici $5 \times 2 \times 3 = 30$.[/reponse]
[/qcm]
[/etape]

Cryptographie – Bac S Pondichéry 2016 (spé)

Partie A

On considère les matrices $ M $ de la forme $ M = \begin{pmatrix}a&b \\ 5&3\end{pmatrix} $ où $ a $ et $ b $ sont des nombres entiers.

Le nombre $ 3a - 5b $ est appelé le déterminant de $ M $. On le note det$ (M) $.

Ainsi det$ (M) = 3a - 5b $.

Dans cette question on suppose que det$ (M) \ne 0 $ et on pose $ N = \dfrac{1}{\text{det}(M)}\begin{pmatrix}3& - b \\ - 5&a\end{pmatrix} $.

Justifier que $ N $ est l'inverse de $ M $.
On considère l'équation $ (E) :\quad \text{det}(M) = 3 $.

On souhaite déterminer tous les couples d'entiers $ (a~;~b) $ solutions de l'équation $ (E) $.
1. Vérifier que le couple $ (6~;~3) $ est une solution de $ (E) $.
2. Montrer que le couple d'entiers $ (a~;~b) $ est solution de $ (E) $ si et seulement si$ 3(a - 6) = 5(b - 3) $.
  
  En déduire l'ensemble des solutions de l'équation $ (E) $.

Partie B

On pose $ Q = \begin{pmatrix}6 & 3 \\ 5 & 3\end{pmatrix} $.

En utilisant la partie A, déterminer la matrice inverse de $ Q $.
Codage avec la matrice $ Q $

Pour coder un mot de deux lettres à l'aide de la matrice $ Q = \begin{pmatrix}6 &3 \\ 5& 3\end{pmatrix} $ on utilise la procédure ci-après :

Étape 1 : On associe au mot la matrice $ X = \begin{pmatrix}x_1 \\ x_2\end{pmatrix} $ où $ x_1 $ est l'entier correspondant à la première lettre du mot et $ x_2 $ l'entier correspondant à la deuxième lettre du mot selon le tableau de correspondance ci-dessous :

A B C D E F G H I J K L M

0 1 2 3 4 5 6 7 8 9 10 11 12

N O P Q R S T U V W X Y Z

13 14 15 16 17 18 19 20 21 22 23 24 25

Étape 2 : La matrice $ X $ est transformée en la matrice $ Y = \begin{pmatrix}y_1 \\ y_2\end{pmatrix} $ telle que $ Y = QX $.

Étape 3 : La matrice $ Y $ est transformée en la matrice $ R = \begin{pmatrix}r_1 \\ r_2\end{pmatrix} $ telle que $ r_1 $ est le reste de la division euclidienne de $ y_1 $ par 26 et $ r_2 $ est le reste de la division euclidienne de $ y_2 $ par 26.

Étape 4 : À la matrice $ R = \begin{pmatrix}r_1 \\ r_2\end{pmatrix} $ on associe un mot de deux lettres selon le tableau de correspondance de l'étape 1.

Exemple : JE

$ \to X = \begin{pmatrix}9 \\ 4\end{pmatrix} \to Y = \begin{pmatrix}66 \\ 57\end{pmatrix} \to R \begin{pmatrix}14 \\ 5\end{pmatrix} \to $

OF.

Le mot JE est codé en le mot OF.

Coder le mot DO.
Procédure de décodage On conserve les mêmes notations que pour le codage.

Lors du codage, la matrice $ X $ a été transformée en la matrice $ Y $ telle que $ Y = QX $.
1. Démontrer que $ 3X = 3Q^{ - 1}Y $ puis que $ \begin{cases} 3x_1 \equiv 3r_1 - 3r_2 \quad [26]\\ 3x_2 \equiv - 5r_1+6r_2 \quad [26] \end{cases} $
2. En remarquant que $ 9 \times 3 \equiv 1 \quad [26] $, montrer que $ \begin{cases} x_1 \equiv r_1 - r_2 \quad [26] \\ x_2 \equiv 7r_1+2r_2 \quad [26] \end{cases} $
3. Décoder le mot SG.

Corrigé

Partie A

On a :

$ NM = \dfrac{1}{\text{det}(M)} \begin{pmatrix} 3 & -b \\ -5 & a \end{pmatrix} \begin{pmatrix} a & b \\ 5 & 3 \end{pmatrix} = \dfrac{1}{3a-5b} \begin{pmatrix} 3a-5b & 3b-3b \\ -5a+5a & -5b+3a \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I $

où $ I $ est la matrice unité de dimension $ 2 \times 2 $. On en déduit que $ N = M^{-1} $.
L'équation $(E)$ est $ 3a - 5b = 3 $.
1. Le couple $(6~;~3)$ est solution car $ 3 \times 6 - 5 \times 3 = 18 - 15 = 3 $.
2. $ 3a - 5b = 3 \iff 3a - 5b = 3 \times 6 - 5 \times 3 \iff 3(a-6) = 5(b-3) $.
  
  5 divise $ 3(a-6) $ et $ \text{PGCD}(5~;~3) = 1 $, donc d'après le théorème de Gauss, 5 divise $ a-6 $.
  
  Il existe donc un entier relatif $ k $ tel que $ a-6 = 5k $, soit $ a = 6 + 5k $.
  
  En remplaçant dans $ 3(a-6) = 5(b-3) $, on obtient $ 3(5k) = 5(b-3) $, soit $ 3k = b-3 $, donc $ b = 3 + 3k $.
  
  L'ensemble des solutions est l'ensemble des couples $(6 + 5k~;~3 + 3k)$ où $ k \in \mathbb{Z} $.

Partie B

D'après la partie A, si $\text{det}(Q) = 3$, alors :

$ Q^{-1} = \dfrac{1}{3} \begin{pmatrix} 3 & -3 \\ -5 & 6 \end{pmatrix} = \begin{pmatrix} 1 & -1 \\ -\dfrac{5}{3} & 2 \end{pmatrix} $
Codage du mot DO

$ D \to 3 $ et $ O \to 14 $. On a $ X = \begin{pmatrix} 3 \\ 14 \end{pmatrix} $.

$ Y = QX = \begin{pmatrix} 6 & 3 \\ 5 & 3 \end{pmatrix} \begin{pmatrix} 3 \\ 14 \end{pmatrix} = \begin{pmatrix} 18+42 \\ 15+42 \end{pmatrix} = \begin{pmatrix} 60 \\ 57 \end{pmatrix} $.

On calcule les restes de la division euclidienne par 26 :

$ 60 = 2 \times 26 + 8 $, donc $ r_1 = 8 \to I $.

$ 57 = 2 \times 26 + 5 $, donc $ r_2 = 5 \to F $.

Le mot DO est codé en IF.
Décodage
1. $ QX = Y \implies Q^{-1}QX = Q^{-1}Y \implies X = Q^{-1}Y $.
  
  En multipliant par 3 : $ 3X = 3Q^{-1}Y $.
  
  $ 3 \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = 3 \begin{pmatrix} 1 & -1 \\ -\dfrac{5}{3} & 2 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} = \begin{pmatrix} 3 & -3 \\ -5 & 6 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} = \begin{pmatrix} 3y_1 - 3y_2 \\ -5y_1 + 6y_2 \end{pmatrix} $
  
  D'où :
  
  $ \begin{cases} 3x_1 = 3y_1 - 3y_2 \\ 3x_2 = -5y_1 + 6y_2 \end{cases} $
  
  Comme $ y_1 \equiv r_1 \pmod{26} $ et $ y_2 \equiv r_2 \pmod{26} $, on en déduit :
  
  $ \begin{cases} 3x_1 \equiv 3r_1 - 3r_2 \pmod{26} \\ 3x_2 \equiv -5r_1 + 6r_2 \pmod{26} \end{cases} $
2. $ 9 \times 3 = 27 \equiv 1 \pmod{26} $.
  
  En multipliant les relations précédentes par 9 :
  
  $ 9 \times 3x_1 \equiv 9(3r_1 - 3r_2) \pmod{26} \implies 27x_1 \equiv 27r_1 - 27r_2 \pmod{26} \implies x_1 \equiv r_1 - r_2 \pmod{26} $.
  
  $ 9 \times 3x_2 \equiv 9(-5r_1 + 6r_2) \pmod{26} \implies 27x_2 \equiv -45r_1 + 54r_2 \pmod{26} $.
  
  Or $ -45 = -2 \times 26 + 7 \equiv 7 \pmod{26} $ et $ 54 = 2 \times 26 + 2 \equiv 2 \pmod{26} $.
  
  D'où $ x_2 \equiv 7r_1 + 2r_2 \pmod{26} $.
3. Décoder le mot SG
  
  $ S \to 18 $ et $ G \to 6 $. On a $ r_1 = 18 $ et $ r_2 = 6 $.
  
  $ x_1 \equiv 18 - 6 = 12 \to M $.
  
  $ x_2$ est le reste de $ 7 \times 18 + 2 \times 6 = 126 + 12 = 138 $ par 26.
  
  $ 138 = 5 \times 26 + 8 $. Donc $ x_2 = 8 \to I $.
  
  Le mot SG se décode en MI.

Congruences – Bac S Amérique du Nord 2009

Soit A l'ensemble des entiers naturels de l'intervalle [1 ; 46].

On considère l'équation

(E) : $ 23x+47y=1 $

où $ x $ et $ y $ sont des entiers relatifs.
1. Donner une solution particulière $ \left(x_{0}, y_{0}\right) $ de (E).
2. Déterminer l'ensemble des couples $ \left(x, y\right) $ solutions de (E).
3. En déduire qu'il existe un unique entier $ x $ appartenant à A tel que $ 23x\equiv 1 \ \left(47\right) $.
Soient $ a $ et $ b $ deux entiers relatifs.
1. Montrer que si $ ab\equiv 0 \ \left(47\right) $ alors $ a\equiv 0 \ \left(47\right) $ ou $ b\equiv 0 \ \left(47\right) $.
2. En déduire que si $ a^{2}\equiv 1 \ \left(47\right) $ alors $ a\equiv 1 \ \left(47\right) $ ou a $ a\equiv - 1 \ \left(47\right) $.
1. Montrer que pour tout entier $ p $ de A, il existe un entier relatif $ q $ tel que $ p \times q\equiv 1 \ \left(47\right) $.
  
  Pour la suite, on admet que pour tout entier $ p $ de A, il existe un unique entier, noté $ \text{inv}\left(p\right) $, appartenant à A tel que
  
  $ p \times \text{inv}\left(p\right)\equiv 1 \ \left(47\right) $.
  
  Par exemple :
  
  $ \text{inv}\left(1\right)=1 $ car $ 1 \times 1\equiv 1 \ \left(47\right) $, $ \text{inv}\left(2\right)=24 $ car $ 2 \times 24\equiv 1 \ \left(47\right) $, $ \text{inv}\left(3\right)=16 $ car $ 3 \times 16\equiv 1 \ \left(47\right) $.
2. Quels sont les entiers $ p $ de A qui vérifient $ p=\text{inv}\left(p\right) $ ?
3. Montrer que $ 46! \equiv - 1 \ \left(47\right) $.

Corrigé

1. Une solution peut être trouvée avec l'algorithme d'Euclide. Ici, elle est évidente:
  
  $ x_{0}= - 2\ ;\ y_{0}=1 $
2. $ 23x+47y=1 \Leftrightarrow 23x+47y=23\times \left( - 2\right)+47\times 1 $
  
  On obtient :
  
  $ 23\left(x+2\right)=47\left(1 - y\right) $
  
  23 et 47 sont premiers entre eux donc d'après le théorème de Gauss 47 divise $ x+2 $
  
  En posant $ x+2=47k\ ;\ k\in \mathbb{Z} $ on trouve que les solutions sont de la forme :
  
  $ \left( - 2+47k~;~1 - 23k\right)\ ;\ k\in \mathbb{Z} $
  
  Réciproquement, vérifier que ces couples sont bien solutions.
3. $ 23x\equiv 1 \ \left(47\right) $ si et seulement si il existe un entier relatif $ y $ tel que:
  
  $ 23x+47y=1 $
  
  On montre à partir du b. qu'il existe une unique solution pour laquelle $ x $ est compris entre 1 et 46 (on peut partir de l'encadrement $ 1\leqslant x\leqslant 46 $ pour trouver un encadrement de $ k $)
  
  Elle correspond à $ k=1 $ et donc $ x=45 $
1. $ ab\equiv 0\ \left(47\right) $ signifie que 47 divise ab.
  
  On applique alors le théorème de Gauss et on arrive rapidement au résultat demandé.
2. $ a^{2}\equiv 1 \ \left(47\right) \Leftrightarrow \left(a - 1\right)\left(a+1\right)\equiv 0 \ \left(47\right) $
  
  Il suffit alors d'appliquer les résultats de la question précédente
1. Comme $ 1\leqslant p\leqslant 46 $, $ p $ et 47 sont premiers entre eux; on peut alors appliquer le théorème de Bézout qui mène directement au résultat recherché.
2. $ p=\text{inv}\left(p\right) \Leftrightarrow p^{2}=1 $
  
  On applique le résultat de 2.b. et compte tenu du fait que $ p\in A $ on trouve
  
  $ p=1 $ ou $ p=46 $
3. $ 46! = 1\times 2\times 3. . . \times 46 $.
  
  A l'exception de 1 et de 46, on peut regrouper les 44 facteurs restants en 22 paires d'entiers "inverses" l'un de l'autre dont le produit vaut 1.
  
  On a donc:
  
  $ 46! \equiv 1\times 46\equiv - 1\ \left(47\right) $

Théorème des restes chinois

On recherche l'ensemble $ S $ des entiers naturels $ n $ qui divisés par 5 donnent un reste égal à 3 et divisés par 7 donnent un reste égal à 2.

Traduire les conditions de l'énoncé à l'aide de congruences.
On pose $ n=5p+3 $ et $ n=7q+2 $.
1. Montrer que $ p $ et $ q $ vérifient l'équation (E) : $ 7q - 5p=1 $
2. Pourquoi l'équation (E) admet-t-elle des solutions dans $ \mathbb{Z}\times \mathbb{Z} $ ?
3. Trouver une solution de (E) dans $ \mathbb{Z}\times \mathbb{Z} $.
4. En déduire l'ensemble des solutions de (E) dans $ \mathbb{N}\times \mathbb{N} $.
En déduire l'ensemble $ S $

Corrigé

Les conditions de l'énoncé se traduisent par :

$ n \equiv 3 \pmod{5} $ et $ n \equiv 2 \pmod{7} $
On pose $ n=5p+3 $ et $ n=7q+2 $.
1. On a $ 5p+3 = 7q+2 $, ce qui équivaut à $ 7q - 5p = 3 - 2 $, soit :
  
  $ 7q - 5p = 1 \quad (E) $
2. Les nombres 7 et 5 sont premiers entre eux car leur PGCD est égal à 1. D'après le théorème de Bézout, il existe donc deux entiers relatifs $ p $ et $ q $ tels que $ 7q - 5p = 1 $. L'équation $(E)$ admet donc des solutions dans $ \mathbb{Z} \times \mathbb{Z} $.
3. On remarque que $ 7 \times 3 = 21 $ et $ 5 \times 4 = 20 $. Comme $ 21 - 20 = 1 $, on en déduit qu'une solution particulière de $(E)$ dans $ \mathbb{Z} \times \mathbb{Z} $ est $(p=4, q=3)$.
4. L'ensemble des solutions de $(E)$ dans $\mathbb{N} \times \mathbb{N}$ est du type $(p=4+7k, q=3+5k)$ avec $ k \in \mathbb{N} $.
  On vérifie aisément que :
  
  $ 7(3+5k) - 5(4+7k) = 21 + 35k - 20 - 35k = 1 $
L'ensemble $ S $ est alors l'ensemble des entiers de la forme :

$ n = 5(4+7k) + 3 = 7(3+5k) + 2 = 23 + 35k \quad \text{avec } k \in \mathbb{N} $