Problème en arithmetique

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour, depuis quelques jours, je bloque sur un problème de math (arithmétique).

Voici l'énoncé : Soit deux entiers naturels a et b avec $a \geq b > 0$. On effectue la division euclidienne de a et de b : on considère donc l'unique couple (q,r) de $\mathbb N^2$ tel que a = qr + b et r<b. Quel est le plus grand entier que l'on peut à la fois ajouter à a et à b sans changer le quotient?

Si je pose n ce plus grand entier alors on a :

$a + n = (b+n)q + r' = bq + nq + r'$ mais je n'arrive pas du tout a trouver r'. J'ai essayé de conjecturer à partir d'exemples mais à chaque fois, je tombe sur un résultat différent.

L'idée c'était de considèrer par la suite $a + (n + 1) = (b + n + 1)(q - 1) + r'' = bq - b + nq - n + q - 1 + r''$ (puisque n est le plus grand entier que l'on peut à la fois ajouter à a et à b sans changer le quotient, au rang supérieur alors le quotient diminue car le diviseur augmente), mais je ne trouve pas r'' non plus.

Si j'avais trouvé les restes, j'aurais obtenu n de cette manière :

$a + (n + 1) = (b + (n + 1))q + r' = bq + nq + q + r' \Leftrightarrow nq + q + r' = - b + nq - n + q - 1 + r''$.

Une idée? Merci d'avance. :-/

Édité par Ozmox

Éternel curieux

+0 -0

Cette réponse a aidé l'auteur du sujet

salut,

en partant de

$$a + n = (b + n) q + r', \quad 0 \leqslant r' < b + n$$

en développant et en simplifiant avec l’identité $a = bq + r$, on trouve :

$$\begin{align*} n &= nq + r' - r \\ r' &= r - (q - 1) n \end{align*}$$

par ailleurs, il faut aussi vérifier l’inégalité $0 \leqslant r' < b + n$. la borne supérieure est satisfaite d’office car $r - (q - 1) n \leqslant r + n < b + n$. pour la borne inférieure, il faut que

$$0 \leqslant r - (q - 1) n$$

tu peux donc dire qu’il faut et il suffit que $n$ soit le plus grand entier naturel satisfiant cette inégalité, c’est‐à‐dire :

$$n = \left\lfloor \tfrac{r}{q-1} \right\rfloor$$

il faut traiter les cas $q = 0$ et $q = 1$ à part. dans ces deux cas, les inégalités précédentes restent vraies pour tout $n$ et donc $n = \infty$ (le cas $q = 0$ correspond à $a < b$ qui était exclu par l’énoncé).

Édité par Maëlan

écrire français sous Windows : fr-oss (azerty++) ou bépo (étudié pour le français) | <insérer un truc spirituel ici>

+1 -0
Auteur du sujet

Merci, l'exercice était pas si subtil mais merci beaucoup pour ton aide. J'aurais peut-être l'occasion de réutiliser un raisonnement similaire. :-)

Éternel curieux

+0 -0
Staff

En prime, tu peux visualiser : quel est l'ensemble des points (b,a) tels que ⎣a/b⎦ = q ?

ρττ

Allez j'essaie.

$$⎣\frac{a}{b}⎦ = q$$

$$\frac{a}{b}=q+\epsilon, \epsilon\in [0,1[$$
$$a=(q+\epsilon)b$$
$$a=q_{\epsilon}b$$

C'est donc un ensemble de droites paramétrées par $\epsilon\in [0,1[$. Donc une sorte de double-cône, de "pointe" confondue avec l'origine, dont l'un des bords appartient à l'ensemble (correspondant à $\epsilon=0$) et l'autre non (correspondant à $\epsilon=1$).

Édité par Algue-Rythme

+0 -0

En effet. On veut les n∈ℕ tels que $q \leq \frac{a+n}{b+n} \leq q+1$. La deuxième inégalité est satisfaite si n≥0 et la première équivaut à q(b+n) ≤ a+n, soit (q-1)n ≤ a-bq.

Géométriquement, on considère la droite y=qx et celle de pente 1 passant par (b,a). On commence avec une distance de r=a-qb et à chaque fois qu'on fait un pas vers la droite, cette distance diminue de q-1 (la différence des deux pentes).

Édité par blo yhg

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte