Congruences & divisibilité


Le but de cet article va être de montrer que le nombre $2^{33}-1$ n'est divisible ni par 4 ni par 3.

Méthode 1

Une première méthode est rapide. Elle consiste à remarquer que $2^{33}$ est pair (2*2*2...*2) et divisible par 4. Donc $2^{33} -1$ est nécessairement impair et non divisible par 4.


Méthode 2 - divisibilité par 4

Maintenant, démontrons le même résultat en utilisant les congruences.

$2^{33} -1 \equiv 2^{33}-1 [4]$

  • Car tout nombre est congru à lui même et ce quel que soit le modulo.

$2^{33} \equiv 2^{33} [4]$

  • On peut ajouter k, entier relatif  de part et d'autre.

$2^{33} \equiv (2^3)^{11} [4]$

$2^{33} \equiv (0)^{11} [4]$

  • Car $2^3 \equiv 8 \equiv 0 [4]$

$2^{33} \equiv 0 [4]$

Et par conséquent :

$2^{33} -1 \equiv -1 [4]$

Or, un nombre a est divisible par n si et seulement si $a \equiv 0 [n]$, c'est à dire si a = kn + 0

Ici, nous avons déterminé que le reste de la division euclidienne de $2^{33} -1$ par 4 valait -1.

Autrement dit, $2^{33} -1 = 4k -1$ ou $2^{33} = 4k$ (ce qui confirme que $2^{33}$ est pair).

Par conséquent,  $2^{33} -1$ n'est pas divisible par 4.

Méthode 2 - divisibilité par 3

Le principe pour démontrer que $2^{33} - 1$ n'est pas divisible par 3 est similaire. En revanche, ce n'est pas parce-que $2^{33} -1$ est impair et 3 également que $2^{33} -1$ est divisible par 3. Ici nous utiliserons donc les congruence exclusivement.

$2^{33} -1 \equiv 2^{33} -1 [3]$

$2^{33} \equiv 2^{33} [3]$

$2^{33} \equiv (2^3)^{11} [3]$

$2^{33} = (-1)^{11} (3)$

  • Car $2^3 \equiv 8 \equiv -1 (3)$

$2^{33} -1 \equiv -2 [3]$

$2^{33} -1 \equiv 1 [3]$

Par conséquent,  $2^{33} -1$ n'est pas divisible par 3.
Clément
Fondateur du blog Point Carré et philognoseur. Ecrit sur des sujets variés, essentiellement pour ses études et parfois juste par plaisir !

Articles populaires

Les sommes : la sommation par paquets

Le principe de la sommation par paquet est de séparer une somme initiale en une somme de sommes (je sais, c'est bizarre !). Par exemple, on peut séparer une somme banale avec d'un côté les nombres pairs et de l'autre les nombres impairs. Cela peut-être d'une aide bienvenue en trigonométrie ou avec $(-1)^k$. Exemple : $$\sum_{k=0}^{2n} k = \sum_{\lceil{k=\frac{0}{2}}\rceil}^{\lfloor{\frac{2n}{2}}\rfloor} 2k + \sum_{\lceil{k=\frac{0}{2}}\rceil}^{\lfloor{\frac{2n-1}{2}}\rfloor} 2k + 1 = \sum_{k=0}^{n} 2k + \sum_{k=0}^{n-1} 2k + 1$$ Le processus pas à pas : Je commence par construire le membre des nombres impairs en soustrayant -1 à droite (j'ajoute donc +1 à gauche). $$\sum_{k=-1}^{2n-1} k + 1$$ Puis, je remplace k par 2k, et donc je divise -1 et 2n par 2. $$\sum_{k=\frac{-1}{2}}^{\frac{2n-1}{2}} 2k + 1$$ Et je termine par les arrondis supérieurs et inférieurs : $$\sum_{k=\lceil{\frac{-1}{2}}\rceil}^{\lfloor{\frac{2n-1}{2}}\rfloor} 2k + 1$$ Je pa
Continuer la lecture

Mo et Mb, différences et conséquences

Image
Vous avez probablement déjà remarqué que l'on parlait tantôt de MégaBits (Mb) et tant ôt de MégaOctet (Mo). Pourquoi cette différence et quelles sont les conséquences pour nous, usager d'internet ? Il suffit pour cela de comprendre la différence entre Byte et Bit. En effet, Mb = Mégabit et MB = Mégabyte. Un bit est la plus petite unité du système informatique (celle qui prend alternativement la valeur 0 ou 1 - le ou est important car dans les ordinateurs quantique, il se transforme en et mais c'est une autre histoire...). Une byte vaut 8 bits. Et un byte vaut également un octet. Pour faire simple, quand il y a un B majuscule, on parle de Byte et quand il y a un b minuscule on parle de bit. Par conséquent, il y a 8 fois moins de "quantité de donnée" dans un Mo que dans un Mb. Or, les Mb sont utilisés pour définir le débit internet. Ainsi, la vitesse maximum d'une carte réseau "standard" (id est équipant la majorité des terminaux
Continuer la lecture

Les démonstrations par récurrence

Image
Le raisonnement par récurrence (avec deux r s'il vous plait) est une méthode de démonstration d'une conjecture, c'est à dire d'une supposition. Une fois la récurrence terminée et la conjecture prouvée, elle deviendra une assertion vraie (sachant qu'une assertion peut-être vraie ou fausse mais pas les deux, c'est le principe dit du "tiers-exclu". Toutefois, les différentes définitions des termes de logique mathématique peuvent parfois différer légèrement et sont sujettes à débat. Le "tiers-exclu" en logique mathématique correspond à la disjonction des propositions p / non p. En clair, sur les deux propositions, l'une des deux est forcément vraie (si p est vraie, alors p est vraie et si p est fausse, non p est vraie...) Si la proposition est vraie à un certain point fixe (ex: n= 1) et, sachant qu'elle est vraie pour un n quelconque elle est aussi vraie pour le n suivant, alors la proposition est vraie pour tous les n plus g
Continuer la lecture