Énigme congruences
dans Arithmétique
Bonjour,
J'ai une question tout ce qu'il y a de plus sérieuse à poser. Je pourrais le faire de façon classique mais, juste pour le plaisir, je vais me permettre de la poser sous la forme d'une énigme, si vous le voulez bien. J'espère seulement ne pas avoir commis d'erreur. Voici cette énigme :
Au dernier recensement de la population, le pays de MathLand comptait exactement $1.048.575$ habitants.
Pour la fête nationale toute proche, il a été prévu que chaque habitant porterait un dossard fourni par l'administration. Ainsi, sur base d'une liste alphabétique des habitants, le premier de ceux-ci a déjà reçu le dossard n°1, le deuxième habitant le dossard n°2, et ainsi de suite jusqu'au dernier.
Au pays de MathLand, on aime rire et s'amuser. Cependant, la loi est dure. Mais c'est la loi :
Sous peine de lourdes sanctions, il sera interdit au porteur du dossard $a$ de faire la fête avec le porteur du dossard $b$ pour peu que, simultanément :
$a+b$ soit congru à $1$ modulo $1.048.576$
$a\times b$ soit congru à $0$ modulo $1.048.576$
Combien de couples $(a;b)$ risquent d'être sanctionnés ?
Merci d'avance.
J'ai une question tout ce qu'il y a de plus sérieuse à poser. Je pourrais le faire de façon classique mais, juste pour le plaisir, je vais me permettre de la poser sous la forme d'une énigme, si vous le voulez bien. J'espère seulement ne pas avoir commis d'erreur. Voici cette énigme :
Au dernier recensement de la population, le pays de MathLand comptait exactement $1.048.575$ habitants.
Pour la fête nationale toute proche, il a été prévu que chaque habitant porterait un dossard fourni par l'administration. Ainsi, sur base d'une liste alphabétique des habitants, le premier de ceux-ci a déjà reçu le dossard n°1, le deuxième habitant le dossard n°2, et ainsi de suite jusqu'au dernier.
Au pays de MathLand, on aime rire et s'amuser. Cependant, la loi est dure. Mais c'est la loi :
Sous peine de lourdes sanctions, il sera interdit au porteur du dossard $a$ de faire la fête avec le porteur du dossard $b$ pour peu que, simultanément :
$a+b$ soit congru à $1$ modulo $1.048.576$
$a\times b$ soit congru à $0$ modulo $1.048.576$
Combien de couples $(a;b)$ risquent d'être sanctionnés ?
Merci d'avance.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Puisque $a(a+b)=a^2+ab$ alors si $(a;b)$ est un couple exclu alors $a^2\equiv a\mod{2^{20}}$
C'est à dire que $a(a-1)$ est divisible par $2^{20}$ et par ailleurs, $a$ et $a-1$ sont premiers entre eux.
Donc, ou bien $a$ est divisible par $2^{20}$ ou bien $a-1$ est divisible par $2^{20}$.
Ce qui est vrai pour $a$, l'est aussi pour $b$.
Réponse:
Deux couples: $(1,2^{20})$ et $(2^{20},1)$
La véritable question contenue dans cette énigme est la suivante :
Dans l'anneau $\mathbb{Z}/m\mathbb{Z}$ ($m$, entier $>1$),
si les idempotents peuvent être unis en couples $(a;b)$ tels que $a+b=1$ et $a\times b=0$,
à l'inverse, tous les couples d'entiers $(a;b)$ tels que $a+b=1$ et $a\times b=0$ y sont-ils obligatoirement des idempotents ?
GaZoBuMeu semble avoir son avis sur la question, le même que le mien (mais j'hésitais quand même encore).
Je précise que le dossard 0 (zéro) n'existe pas.
Mais le dossard $2^{20}$ existe bien. Cela ne change rien à ma réponse.
PS:
Pour répondre à ta question. Oui. Dans le cadre que tu donnes (cf mon message plus haut)
Puisque $a(a+b)=a^2+ab$ et $b(a+b)=ba+b^2$
Gill Bill:
Alors il y a aucun couple exclu.
Ceci étant, la preuve a été donnée par Fin de partie. J'aurais plutôt écrit : $a^2-a\equiv a(1-a)\equiv ab\equiv0\mod m$ (ou bien $a^2-a=a(1-a)=ab=0$ dans $\Z/m\Z$).
La loi édictée n'était qu'une petite plaisanterie administrative.
:-)