Travaux Dirigés de Structures Discrètes n^{o} 5

— Licence Informatique —

▶ Exercice 1 (Changement de base)

• Convertir les nombres binaires suivants en base 10 : (1010)_{2}, (100101)_{2}, (10000001)_{2}.

• Convertir de la base 10 à la base 2 les entiers : 82, 109, 3433. ▶ Exercice 2 (Décomposition en facteurs premiers) Décomposer les entiers suivants en facteurs premiers : 56, 323, 720, 2613, 2171. ▶ Exercice 3 (Calcul du plus grand commun diviseur) Calculer le pgcd et les coefficients de Bezout associés pour les exemples suivants :

1. 26, 19;

2. 72, 40;

3. 186, 68;

4. 187, 34;

5. 841, 160;

6. 2613, 2171; ▶ Exercice 4 On se donne deux entiers positifs a et b. Expliquer pourquoi, si l’on trouve c et d tels que ac + bd = 1, on peut conclure que a et b sont premiers entre eux. ▶ Exercice 5 Soit k un entier relatif. Déterminer 9k + 4 ∧ 2k + 1 puis 9k + 4 ∧ 2k − 1. ▶ Exercice 6 (Critères de divisibilité) On pose nℤ = {nk}_{k∈ℤ}, ensemble des multiples de n. On rappelle le théorème de division euclidienne (dans ℤ) : pour n ≥ 1, ∀a ∈ ℤ, ∃(q, r), q ∈ ℤ, r ∈ {0, 1, …, n − 1}, a = nq + r. De plus le couple (q, r) est unique. On note par ailleurs, r_{n}(a) := r.

1. montrer que a_{1} − a_{2} ∈ nℤ ⇔ r_{n}(a_{1}) = r_{n}(a_{2}); on note alors a_{1} ≡ a_{2} [n] et on dit a_{1} est congru à a_{2} modulo n.

2. montrer que

\begin{matrix}a_{1} & ≡ & a_{2} [n] \\ & et \\ b_{1} & ≡ & b_{2} [n] \end{matrix} \} ⇒ \{ \begin{matrix}a_{1}b_{1} & ≡ & a_{2}b_{2} [n] \\ & et \\ a_{1} + b_{1} & ≡ & a_{2} + b_{2} [n] \end{matrix}

3. déduire que (α_{n}α_{n−1} … α_{0})_{10} ≡ α_{n} + α_{n−1} + ⋯ + α_{0} [9];

4. montrer que (α_{n}α_{n−1} … α_{0})_{10} ≡ α_{0} − α_{1} + ⋯ + (−1)^{n}α_{n} [11];

5. en déduire les critères de divisiblité par 3, 9 et 11; 6. démontrer les critères classiques de divisibilité par 4, 5 et 25;

7. imaginer un critère simple de divisibilité par 275. ▶ Exercice 7 Montrer que tout carré est égal à 4k ou 4k + 1. ▶ Exercice 8 Montrer que tout entier congru à 7 modulo 8 n’est pas somme de trois carrés. ▶ Exercice 9 Montrer que si p est premier et p est la somme de 2 carrés, alors p est de la forme 4k + 1. ▶ Exercice 10 Montrer que tout entier positif de la forme 3n+2 est divisible par un nombre premier de la même forme. ▶ Exercice 11 Soit n un entier. Montrer que n^{5} − 5n^{3} + 4n est divisible par 120. ▶ Exercice 12 Plus généralement, soient a et n deux entiers naturels. Montrer que n! divise le produit (a + 1)(a + 2) … (a + n). ▶ Exercice 13 Soient a et b deux entiers strictement positifs. Trouver tous les entiers strictement positifs c tels que chacun des trois nombres a, b et c divise le produit des deux autres. Traiter le cas a = 42 et b = 30.