Forum de mathématiques - Bibm@th.net

Vani94

Membre

Inscription : 04-11-2022

Messages : 26

Congruence et critère de divisibilité

Bonjour,
Je bloque sur mon exercice de maths, pourriez-vous m'aider, s'il vous plaît ?
Voici l'énoncé :
Pour savoir si un entier naturel n est divisible par 7, on sépare le chiffre des unités de n des autres chiffres et on effectue la différence entre le nombre formé par les autres chiffres et le double du chiffre des unités. L'entier n est divisible par 7 si est seulement si cette différence est divisible par 7.

Exemple : 861 est-il divisible par 7 ?
On effectue 86-2×1=84 puis 8-2×4=0 qui est divisible par 7 donc 84 également, donc 861 également en appliquant deux fois le critère.

Dans cette exercice, on se propose de démontrer ce critère pour un nombre de trois chiffres.
Soit n un entier naturel de trois chiffres dont l'écriture décimale est n= $\bar {abc}$ avec a # 0

1) Démontrer que n congru à 2a+3b+c [7]
2) on appelle m l'entier égal à la différence décrite ci-dessus. Montrer que : m congru à 3a+b-2c [7]
3) En déduire que : n-3m congru à 0 [7] et que m+2n congru à 0 [7]
4) En déduire que : m congru à 0 [7] est équivalent à n congru à 0 [7]
5) Conclure

Pour l'instant j'ai juste émis des hypothèses pour la question 1) :

. Pour démontrer que n congru à 2a+3b+c [7] il faut démontrer que n et 2a+3b+c ont le même reste dans la division euclidienne par 7.
. que si n = $\bar {abc} $ alors l'écriture sous système décimale de n est : $a×10^2 + b×10+c ×10^0$ = 100a +10b+c.
. Pour que n soit divisible par 7 il faut que le résultat de 100a +10b -2c soit divisible par 7. De même pour que 2a+3b+c soit divisible par 7 il faut que le résultat de 2a+3b -2c soit divisible par 7.

Mais sinon après je suis un peu bloquée.

Ginger40

Membre

Inscription : 22-11-2022

Messages : 35

Re : Congruence et critère de divisibilité

Bonjour,

. Pour démontrer que n congru à 2a+3b+c [7] il faut démontrer que n et 2a+3b+c ont le même reste dans la division euclidienne par 7.

C'est effectivement un moyen de montrer une congruence ! Mais n'oublie pas une définition équivalente (et souvent plus facile) qui est de dire :
$$
a \equiv b [n] \iff n|a-b \iff n|b-a
$$
Je conseille donc d'écrire la différence $n-(2a+3b+c)$ (en utilisant la bonne remarque que $n=100a+10b+c$) et d'étudier les termes de manière isolée.

Les questions 2. et 3. se traitent de manière similaire, mais attention :

. Pour que n soit divisible par 7 il faut que le résultat de 100a +10b -2c soit divisible par 7.

Ce n'est pas ça que dit la propriété. Si on revient au cas particulier de $861$ on peut voir qu'il y a une différence (d'ailleurs il est interdit d'utiliser ce résultat pour l'instant vu qu'on cherche à le démontrer !).
Aussi,

De même pour que 2a+3b+c soit divisible par 7 il faut que le résultat de 2a+3b -2c soit divisible par 7.

Non plus, mais là c'est un peu plus subtil. En fait il faut toujours revenir à une forme $100a_1 + 10a_2 + a_3$ pour avoir une notion d'unité, dizaine et centaine. Ici, on ne peut pas savoir les chiffres d'unité, dizaine et centaine de $2a+3b+c$ car on ne connaît pas les valeurs de $a,b,c$.
Par exemple $2*1+3*1+2=7$ et $2*3+3*1+2=11$. On peut voir ici que l'unité du nombre n'est pas $c$ et que la "partie gauche" n'est pas $2a+3b$.

Dernière modification par Ginger40 (19-12-2022 15:58:36)

Vani94

Membre

Inscription : 04-11-2022

Messages : 26

Re : Congruence et critère de divisibilité

Bonjour Ginger40,

On peut donc dire que si n congru à 2a+3b+c [7] est équivalent à dire que 7 divise n-(2a+3b+c) et donc que 7 divise (2a+3b+c)-n, ainsi la différence s'écrit :
n-(2a+3b+c) = 100a+10b+c-(2a+3b+c)=100a+10b+c-2a-3b-c = 98a-7b

Ainsi 7 divise 98a+7b  or 98=14×7 +0 et 7= 7×1+0
donc n-(2a+3b+c) = 98a+7b qui est congru à 0 [7] ??

Ginger40

Membre

Inscription : 22-11-2022

Messages : 35

Re : Congruence et critère de divisibilité

Oui c'est exactement ça l'idée !

Attention par contre à la logique et à bien mettre toutes les justifications.
Il ne faut pas écrire :

Ainsi 7 divise 98a+7b

en plein milieu du raisonnement : c'est quelque chose qu'on aimerait montrer justement.
Ce qui a, à ce stade du raisonnement, été démontré s'exprime de la manière suivante :
"$n\equiv 2a+3b+c \: [7]$ si et seulement si (on peut aussi dire 'est équivalent à') $7|98a+7b$".

Enfin il ne faut pas oublier de bien justifier que :
$$
\begin{array}\\
98 \equiv 0 [7] \Rightarrow 98a \equiv 0 [7] \\
7 \equiv 0 [7] \Rightarrow 7b \equiv 0 [7]\\
\end{array}
$$
Et donc que $98a+7b \equiv 0 [7]$ par linéarité.

Vani94

Membre

Inscription : 04-11-2022

Messages : 26

Re : Congruence et critère de divisibilité

D'accord merci beaucoup pour votre aide,

De ce fait pour la question 2, si on part du même principe :
m congru à 3a+b-2c [7] revient à dire que 7 divise m-(3a+b-2c) et que 7 divise (3a+b-2c)-m
Or si m est la différence entre le double du chiffres des unités et le nb formé par les autres chiffres d'un entier n, alors : pour un entier n tel que n = 100a+10b+c et que n congru à 2a+3b+c [7] si et seulement si 7 divise 98a+7b,

On peut dire que 98a+7b est congru à 3a+b-2c [7] ??
Ainsi 98a+7b-(3a+b-2c) = 95a+6b+2c
Or 95 congru à 4 [7] , 6 congru à 6 [7] et 2 congru à 2[7].

Dernière modification par Vani94 (19-12-2022 18:53:00)

Ginger40

Membre

Inscription : 22-11-2022

Messages : 35

Re : Congruence et critère de divisibilité

On a d'abord montré dans la question 1. que $n\equiv 2a+3b+c [7]$, et on laisse ça de côté pour l'instant (ça nous servira plus tard).

Le début de la question 2. est bien : on veut effectivement montrer que $7|(3a+b-2c)-m$.
Ce qu'il faut faire à partir de là c'est trouver comment exprimer $m$. Ce que je veux dire par là c'est que si on note $n=\overline{abc}^{10} = 100a + 10b + c$, comment peut-on exprimer $m$ avec $a,b,c$ ? (Sachant que la définition de $m$ est : " la différence entre le nombre formé par les autres chiffres et le double du chiffre des unités")

Comme j'ai dit plus haut, on pourra vérifier sur le cas particulier de $861$ pour être sûr de la formule.

Vani94

Membre

Inscription : 04-11-2022

Messages : 26

Re : Congruence et critère de divisibilité

Dans ce cas,
Pour un entier n tel que $n=\overline{abc}$, la différence m tel que m est égal à la différence du nombre formé par les autres et chiffres et le double du chiffre des unités est : $m=\overline{ab}-2c$ ??

Ginger40

Membre

Inscription : 22-11-2022

Messages : 35

Re : Congruence et critère de divisibilité

Oui ça commence bien.
Maintenant, il faut aussi écrire $\overline{ab}$ de la bonne manière (comme pour $n = 100a+10b+c$) puis le tour est joué !

Vani94

Membre

Inscription : 04-11-2022

Messages : 26

Re : Congruence et critère de divisibilité

Ah je vois donc on peut écrire que :

Si $\overline{abc} = 100a +10b+ c $ ,alors, $\overline{ab} = a ×10 + b × 10^0 = 10a+b$.
Ainsi m = $10a +b -2c$

(En vérifiant avec $861: 10×8+6-2×1= 84$ et $10×0+8-2×4=0$, l'expression est donc vérifiée)

De ce fait : $3a +b -2c - m = 3a +b -2c-(10a +b -2c)= -7a$
Or$ -7 = (-1)×7+0 $ donc $-7 $ congru à $0 [7] $ qui est équivalent à dire que $ -7a$ congru à $0 [7]$.
Ainsi m congru à $3a +b -2c [7]$ si $7$ divise $-7a $ ?

Ginger40

Membre

Inscription : 22-11-2022

Messages : 35

Re : Congruence et critère de divisibilité

Oui c'est cela !
Comme $-7a = 7\times (-a)+0$ on a bien que $7|-7a$ et ainsi $m \equiv 3a+b-2c [7]$ !
La question 3. c'est pareil, mais il faut surtout penser à utiliser ce que l'on vient de faire et ne pas repartir avec les grosses expressions de $n$ et $m$ (ça serait dommage !).
Pour la question 4. il faut se servir de la linéarité et bien démontrer que c'est une équivalence (un sens, puis l'autre).

Vani94

Membre

Inscription : 04-11-2022

Messages : 26

Re : Congruence et critère de divisibilité

Donc pour la 3 :
Si $n-3m$ congru à $0[7]$ et $m+2n$ congru à $0[7]$.
Alors , $7$ divise $n-3m$ et $7$ divise $3m-n$ , de même $7$ divise $m+2n$.
Or $n$ congru à $2a+3b+c [7]$ et $m$ congru à $3a+b-2c [7]$
Donc $n-3m = 2a+3b+c - 3(3a+b-2c)$$ =  2a+3b+c-9a-3b+6c= -7a +7c$.

Or $-7a$ congru à $0 [7]$ et $7c$ congru à $0 [7]$ (car $7= 7×1+0$)
Ainsi $n-3m$ congru à $0 [7]$.

De même : $m+2n = 3a+b-2c +2(2a+3b+c)=7a+7b$
Or $7a$ congru à $0 [7]$ et $7b$ congru à $0[7]$(car $7= 7×1+0$)
Ainsi $m+2n$ congru à $0 [7]$.

Pour la 4 : on sait que $n-3m$ congru à $0 [7]$ et que $m+2n$ congru à $0 [7]$.
De ce fait, $n$ congru à $3m [7]$ et que $m$ congru à $-2n [7]$. Cela revient donc a dire que $7$ divise $n-3m$ et que $7$ divise $m-(-2)n$ et donc $7$ divise $m+2n$.

Or $n-3m$ congru à $0 [7]$ et $m+2n$ congru à $0 [7]$ donc m congru à $0[7]$ et équivalent à $n$ congru à $0[7]$

Pour la 5 :
on peut donc conclure que le critère de divisibilité a été démontré pour un nombre à 3 chiffres et donc que ce critère fonctionne pour tout nombre à 3 chiffres.

Ginger40

Membre

Inscription : 22-11-2022

Messages : 35

Re : Congruence et critère de divisibilité

C'est nickel pour la question 3 !
Par contre il y a un problème de raisonnement pour la question 4 : on tourne en rond.

on sait que $n-3m$ congru à $0 [7]$ et que $m+2n$ congru à $0 [7]$.
De ce fait, $n$ congru à $3m [7]$ et que $m$ congru à $-2n [7]$. Cela revient donc a dire que $7$ divise $n-3m$ et que $7$ divise $m-(-2)n$ et donc $7$ divise $m+2n$.

Vous partez de $n-3m \equiv 0 [7]$ et $m+2n \equiv 0 [7]$ pour juste après revenir à ces mêmes hypothèses et conclure en disant :

Or $n-3m$ congru à $0 [7]$ et $m+2n$ congru à $0 [7]$ donc m congru à $0[7]$ et équivalent à $n$ congru à $0[7]$

Il n'y a rien qui est démontré...

Pour montrer l'équivalence entre $m\equiv 0 [7]$ et $n \equiv 0 [7]$ cela se fait en 2 étapes :
1. Supposer que $m\equiv 0[7]$ et montrer que $n\equiv 0 [7]$
2. Supposer que $n\equiv 0[7]$ et montrer que $m\equiv 0 [7]$

Pour cela on pourra, en partie, utiliser la compatibilité avec l'addition i.e. :
$$
\left\{
\begin{array}\\
a \equiv b [n] \\
c \equiv d [n] \\
\end{array}
\right.
\Rightarrow a+c \equiv b+d [n]
$$
(J'ai parlé de linéarité plus haut, mais c'est le mauvais terme)

Dernière modification par Ginger40 (20-12-2022 16:08:44)

Vani94

Membre

Inscription : 04-11-2022

Messages : 26

Re : Congruence et critère de divisibilité

Mais du coup je ne comprends pas trop on doit partir de quoi pour la question 4, parce que si on part de $m\equiv 0[7]$ on doit utiliser $n-3m\equiv 0[7]$ pour montrer que $n\equiv 0[7]$ et si on part de $n\equiv 0[7]$ on doit utiliser $m+2n \equiv 0 [7]$ pour montrer que $m\equiv 0[7]$.
Mais si on suppose avec la méthode de comptabilité avec l'addition on trouve que $m +n \equiv 0[7]$ ?

Ginger40

Membre

Inscription : 22-11-2022

Messages : 35

Re : Congruence et critère de divisibilité

Si vous ne comprenez, c'est qu'il y a un problème au niveau de la logique.
Ici, il y a un petit résumé de ce qu'il faut savoir sur la logique.

Dans notre cas on peut dire que $\mathcal{P}$ est la proposition "$m\equiv 0 [7]$" et $\mathcal{Q}$ la proposition "$n\equiv 0[7]$"
On veut donc montrer $\mathcal{P} \iff \mathcal{Q}$, et pour cela on va procéder par double implication.
Je vais faire l'implication $\mathcal{P} \Rightarrow \mathcal{Q}$ pour montrer l'exemple.

Je suppose que la proposition $\mathcal{P}$ est vraie. Je suppose donc que l'on a $m\equiv 0 [7]$.
Maintenant, comme $m\equiv 0 [7]$ on a $3\times m \equiv 3\times 0 [7]$ et donc :
$$
3m \equiv 0 [7]
$$

On se retrouve donc avec :
$$
\left\{
\begin{array}\\
3m \equiv 0 [7] \\
n - 3m\equiv 0 [7]\\
\end{array}
\right.
$$
Et donc en additionnant $n-3m+3m \equiv 0+0 [7]$, c'est-à-dire :
$$
n\equiv 0 [7]
$$

J'espère que c'est assez clair et que ça vous permettra de conclure !

Vani94

Membre

Inscription : 04-11-2022

Messages : 26

Re : Congruence et critère de divisibilité

Donc si je reprends votre méthode :
On suppose que la proposition $\mathcal{Q}$ est vraie et  donc que l'on a $n\equiv 0 [7]$.
comme $n\equiv 0 [7]$ on a $2\times n \equiv 2\times 0 [7]$ et donc :
$$
2n \equiv 0 [7]
$$

On se retrouve donc avec :
$$
\left\{
\begin{array}\\
2n \equiv 0 [7] \\
m + 2n\equiv 0 [7]\\
\end{array}
\right.
$$
Et donc par soustraction $m+2n-2n \equiv 0-0 [7]$, c'est-à-dire :
$$
m\equiv 0 [7]
$$

Donc $m\equiv 0 [7] \iff n\equiv 0 [7]$

Ainsi on a pu démontrer le critère de divisibilité par 7 pour un nombre de 3 chiffres

Ginger40

Membre

Inscription : 22-11-2022

Messages : 35

Re : Congruence et critère de divisibilité

Voilà c'est cela !
C'est en général de cette manière que l'on montre une équivalence (on peut aussi directement faire d'équivalence en équivalence, mais c'est souvent plus compliqué)

Vani94

Membre

Inscription : 04-11-2022

Messages : 26

Re : Congruence et critère de divisibilité

D'accord merci beaucoup pour votre aide !