Exercices corrigés - pgcd, ppcm, nombres premiers entre eux
Enoncé 

- Quels sont les diviseurs communs à 390 et 525?
- Calculer $(3^{123}-5)\wedge 25$.
- Soit $n\in\mathbb Z$. Démontrer que $6|n(n+1)(n+2)$.
Enoncé 

Résoudre les équations suivantes dans $\mathbb Z^2$ :
- $2x+5y=3$;
- $323x-391y=612$;
- $162x+207y=27$;
- $221x+247y=15$.
Enoncé 

Soient $a$ et $b$ deux rationnels tels que $a+b$ et $a\times b$ sont des entiers. Prouver que $a$ et $b$ sont des entiers.
Enoncé 

- Démontrer que si deux entiers relatifs sont premiers entre eux, leur somme et leur produit sont premiers entre eux. La réciproque est-elle vraie?
- Démontrer que l'on ne change pas le pgcd de deux entiers en multipliant l'un d'entre eux par un entier premier avec l'autre.
Exercice 5 
- Points à coordonnées entières sur une droite rationnelle [Signaler une erreur] [Ajouter à ma feuille d'exos]


Enoncé 

Le plan est muni d'un repère $(O,\vec i,\vec j)$. On considère 4 entiers relatifs non nuls $m,n,p$ et $q$ tels que $\textrm{pgcd}(m,n)=\textrm{pgcd}(p,q)=1$. Le but de l'exercice est de déterminer une condition nécessaire et suffisante portant sur $m,n,p,q$ pour que la droite $\Delta$ d'équation $y=\frac mn x-\frac pq$ comporte au moins un point dont les coordonnées sont deux entiers relatifs.
- On suppose dans cette question que la droite $\Delta$ comporte un point de coordonnées $(x_0,y_0)$ où $x_0$, $y_0$ sont des entiers relatifs.
- Démontrer que $q$ divise le produit $np$.
- En déduire que $q$ divise $n$.
- Réciproquement, on suppose que $q$ divise $n$ et on souhaite trouver un couple $(x_0,y_0)$ d'entiers relatifs tels que $y_0=\frac mnx_0-\frac pq$.
- On pose $n=qr$, où $r$ est un entier relatif non nul. Démontrer que l'on peut trouver deux entiers relatifs $u$ et $v$ tels que $qru-mv=1$.
- En déduire qu'il existe un couple $(x_0,y_0)$ d'entiers relatifs tels que $y_0=\frac mn x_0-\frac pq$.
- On donne l'algorithme suivant :
Variables :
m,n,p,q entiers relatifs non nuls tels que pgcd(m,n)=pgcd(p,q)=1
x entier naturel
Algorithme
Si q divise n alors
x prend la valeur 0
Tant que (mx/n - p/q) n'est pas un entier et (-mx/n-p/q) n'est pas un entier faire
x prend la valeur x+1
Fin Tant Que
Si (mx/n-p/q) est entier alors Afficher x, mx/n-p/q
Sinon Afficher -x,-mx/n-p/q
Fin Si
Sinon Afficher "Pas de solutions"
Fin Si.Justifier que cet algorithme se termine. Que permet-il d'obtenir?
Enoncé 

La machine allemande G-Schreiber était une machine à chiffrer utilisée par l'Allemagne pendant la Seconde Guerre Mondiale. Elle était constituée (entre autres) de dix roues comprenant respectivement 47, 53, 59, 61, 64, 65, 67, 69, 71 et 73 positions. A chaque fois qu'un caractère était tapé, il était chiffré à l'aide d'un algorithme un peu compliqué utilisant la position des roues, puis toutes les roues tournaient d'une position. Combien fallait-il taper de caractères pour revenir à la position initiale des roues?
Enoncé 

Calculer le pgcd de $2^{445}+7$ et $15$.
Enoncé 

Soient $n\in\mathbb Z$. Calculer les pgcd suivants :
$$\begin{array}{lll}
\mathbf 1.\ (n^2+n)\wedge (2n+1)&\quad\quad&\mathbf 2.\ (15n^2+8n+6)\wedge(30n^2+21n+13)\\
\end{array}
$$
Enoncé 

Soient $a,b>0$ deux entiers premiers entre eux et $x>ab$. Montrer que l'équation
$au+bv=x$ a deux solutions avec $a,b\in\mathbb N$.
Enoncé 

J'ai une pile de livres. Lorsque je les range par 10, il m'en reste 3. Lorsque je les range par 17(!), il m'en reste 2. Quel est le nombre minimum de livres que je possède? Quels sont tous les nombres possibles?
Enoncé 

Bonjour, je suis le magicien des mathématiques.
Je vais deviner votre date de naissance.
Prenez votre jour de naissance. Multipliez le par 31.
Prenez votre mois de naissance. Multiplier le par 12.
Ajoutez ces deux nombres. Combien trouvez-vous? 811 vous me dites?
Et bien vous êtes né un 25 mars!
En plus, c'est vrai. Mais comment a-t-il fait?
Prenez votre jour de naissance. Multipliez le par 31.
Prenez votre mois de naissance. Multiplier le par 12.
Ajoutez ces deux nombres. Combien trouvez-vous? 811 vous me dites?
Et bien vous êtes né un 25 mars!
En plus, c'est vrai. Mais comment a-t-il fait?
Enoncé 

Montrer que l'équation $x^3-x^2+x+1=0$ n'a pas de solutions dans $\mathbb Q$.
Enoncé 

Soit $(u_n)$ la suite d'entiers définie par $u_0=14$ et $u_{n+1}=5u_n-6$. Démontrer que le pgcd de deux termes
consécutifs de la suite est constant. Préciser sa valeur.
Exercice 14 

- pgcd et somme ou produit prescrits [Signaler une erreur] [Ajouter à ma feuille d'exos]



Enoncé 

- Déterminer les couples d'entiers naturels de pgcd 18 et de somme 360.
- Déterminer les couples d'entiers naturels de pgcd 18 et de produit 6480.
Enoncé 

- Résoudre le système $$\left\{ \begin{array}{rcl} x\wedge y&=&18\\ x\vee y&=&540 \end{array}\right.$$ avec $(x,y)\in\mathbb N^2$.
- Généralisation : trouver une condition nécessaire et suffisante sur $d$ et $m$ pour qu'il existe $(x,y)\in\mathbb N^2$ tels que $x\wedge y=d$ et $x\vee y=m$.
Enoncé 

Trouver tous les couples d'entiers $(x,y)\in\mathbb N^2$ tels que $x\vee y+11(x\wedge y)=203$.
Enoncé 

Soient $a,m,n\in\mathbb N^*$ avec $a\geq 2$ et $m\leq n$. On note $d=(a^n-1)\wedge (a^m-1)$ et $r$ le reste dans la division euclidienne de $n$ par $m$.
- Montrer que $a^n\equiv a^r\ [a^m-1]$.
- En déduire que $d=(a^r-1)\wedge (a^m-1)$, puis que $d=a^{n\wedge m}-1$.
- A quelle condition $a^m-1|a^n-1$?
Enoncé 

Le but de cet exercice est de démontrer que $\sqrt 2$ est irrationnel en utilisant l'algorithme d'Euclide.
On raisonne par l'absurde et on suppose qu'il existe deux entiers strictement positifs $a$ et $b$ tels que $\sqrt
2=a/b$. On pose $c=\sqrt 2+1$.
- Vérifier que $a=b+\frac bc$, puis que $c=2+\frac 1c$.
- Démontrer que $\frac bc$ est un entier, et qu'il est égal au reste $r_1$ de la division euclidienne de $a$ par $b$. Quel est le quotient $q_1$ de cette division?
- Montrer que dans la division euclidienne de $b$ par $r_1$, le quotient est $q_2=2$ et le reste est $r_2=\frac{r_1}c$.
- Soit $n$ un entier supérieur ou égal à 2. Démontrer que l'algorithme d'Euclide appliqué au couple $(a,b)$ comporte au moins $n$ étapes, que le $n$-ième quotient est $q_n=2$, et que le $n$-ième reste est $r_n=\frac{r_{n-1}}c$.
- Conclure.