Une congruence

yan2 · May 2017

Bonjour

On demande le nombre d'entiers $n\in\{1,2,\ldots,100\,000\}$ qui vérifient : $$
11\times 2^{n-1}\equiv 4n+6\pmod{13}.
$$ Je viens de montrer que c'est $7\,693$, mais je ne suis [pas] très satisfait de mon approche.
Quelqu'un a-t-il peut-être une démonstration courte et élégante ? (voire une généralisation en remplaçant $100\,000$ par un entier $N$ quelconque).

Cordialement,
Yan2

Dom · May 2017

Je ne vais pas être d'une grande aide mais j'obtiens : $$2^{n-2}+n+8=0\pmod{13}.
$$ Est-ce utile ?

yan2 · May 2017

j'ai montré qu'il y a $12$ solutions dans chaque intervalle de $12\times 13=156$ entiers. Ensuite, comme $100\,000\equiv 4\pmod{12\times 13}$, il suffit de vérifier (à la main) les valeurs $n=0,1,2,3,4$. Il est facile de voir que seul le $3$ donne lieu à une solution supplémentaire.
En conclusion, il y a : $12\times 641+1=7\,693$ solutions.

flipflop · May 2017

Edit : c'est faux !

On peut regarder la périodicité si je change $n$ en $n+13$, alors $n$ est une solution ssi $n+13$ est solution.

Ensuite, beh on regarde les $13$ premiers termes, il n'y a qu'un seul solution (c'est 3). Du coup, pour $N$ on peut faire la division de $N$ par $13$ : $N=13*q+r$ alors le nombre de solution est $q+\alpha$ avec $\alpha = 0$ si $r=0,1,2$ et sinon $\alpha$ faut $1$.

flipflop · May 2017

@Yan2 : je pense que j'ai écrit la même chose que toi ! Le truc, c'est que tu sembles compter les solutions dans l'intervalle $[1,12 \times 13]$, c'est bien ça ?

yan2 · May 2017

oui c'est bien ça flipflop, merci

Fin de partie · May 2017

Le résultat est correct, c'est bien 7693 la réponse.

(vérifié par ordinateur).

flipflop · May 2017

@ Yan : J'ai fais une boulette dans mon truc !

Ce n'est pas " $n$ est solution ssi $n+13$ est solution", c'est plutôt que le nombre de solution dans $[1,N]$ est calculable avec une période de $13$.

claude quitté · May 2017

@flip flop
Oui, ton dernier post. Il faut se méfier du fait que $m \mapsto 2^m \bmod 13$ est périodique de période 12 (et pas 13). Ceci parce ce que $2^{12} \equiv 1 \bmod 13$.

flipflop · May 2017

Oui c'est bien ça ma boulette ! Du coup, j'ai rien de mieux que compter $156$ comme toi Yan !

flipflop · May 2017

Je retente un petit truc : en espérant que je n'ai pas fait encore une grosse boulette (td)

Je recherche le nombre de solution de l'équation dans un intervalle $[13q+1, 13 (q+1)]$

Alors si

$q = 0,1,3 \pmod{12}$ il y a $1$ solution.
si $q =4,7,10 \pmod{12}$ il y a $2$ solutions
si $q = 2 \pmod{12}$, il y a $3$ solutions
et $0$ sinon.

Si on prend $[1,12*13]$ on le découpe en intervalle de longueur $13$ : $$[1,12\times13] = \coprod_{q=0}^{12} \big[13q+1, 13 (q+1)\big]$$ et on retrouve bien les $12 = 3 *1 + 3*2+1*3$ solutions !

Du coup, pour $N = 235469 = 1509 \times 156 +65$, on a : $12*1509+1+1+3+1+2$ solutions ...

Le truc pour $N$ quelconque c'est que si le reste n'est pas divisible par $13$, je n'ai pas trouvé de moyen de faire le comptage proprement !

Une congruence

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 24