Congruence

[Theo2732]

Hello quelqu’un sait comment faire ça ?
Déterminer tous les entiers positifs “n” pour lesquels il existe un entier “a” tel que (2^n)-1 divise (a^2) +9.
Merci à tous

[tournesol]

Je n'ai pas cherché mais l'énoncé est équivalent a -9 est reste quadratique modulo 2^n-1 .
Donc symbole de Legendre ouJacobi pour piste ?

[Theo2732]

Merci beaucoup je vois toujours pas vraiment comment faire. Si tu as le temps de m’expliquer...merci

[GaBuZoMeu]

Demandons à SageMath quels sont les entiers n<200 tels que -9 soit un carré modulo 2^n-1 :

Code: Tout sélectionner

[n for n in range(1,200) if Mod(-9,2**n-1).is_square()]

[1, 2, 4, 8, 16, 32, 64, 128]

Bizarre. Est-ce que ça marche encore pour 256 ?

Code: Tout sélectionner

Mod(-9,2**256-1).is_square()

True

Et si on essaie un autre entier que -9 ?

Code: Tout sélectionner

[n for n in range(1,200) if Mod(5,2**n-1).is_square()]

[1, 5, 13, 17, 25, 53, 61, 65, 73, 85, 89, 101, 125, 137, 149]

-9 a l'air bien spécial, et on a envie de formuler une conjecture à son sujet.
Yapuka démontrer la conjecture.

[Ben314]

Salut,
Si n'est pas une puissance de 2 alors il est divisible par un entier impair et est divisible par . Comme il est divisible par (au moins) un nombre premier avec car est impair.
Pour un tel l'entier 9 est un carré inversible modulo mais -1 n'est pas un carré donc -9 n'est pas un carré modulo et ce n'est donc pas un carré modulo .

Si avec alors, pour et , l'entier -9 est bien un carré modulo puis, vu que où les deux facteurs sont premiers entre eux, pour montrer par récurrence que -9 est un carré modulo il suffit de montrer que, pour , c'est un carré modulo c'est à dire que -1 est un carré modulo vu que 9 est un carré inversible modulo .
Et c'est clairement le cas vu que et que .

[Theo2732]

Et ducoup quelles sont les solutions?

[GaBuZoMeu]

Relis avec attention ce que Ben314 a écrit. Tu peux aussi avoir l'idée des solutions en relisant ce que j'ai écrit.

[Theo2732]

Parceque moi j’ai trouvé que les solutions à l’aide d’exel étaient:
Soit n=1 et donc a appartient à Z
Soit n=2 et a=3k, k appartient à Z
Soir n=4 et à=3k, k appartient à Z