Infinité de $n \in \mathbb{N}$ tels que $b | u^n - n - y$

Martin545445

Soient $y, b \in \mathbb{N}$. Pour quel $u \in \mathbb{Z}$ existe-t-il une infinité de $n \in \mathbb{N}$ tels que $b | u^n - n - y$ ?

lesmathspointclaires

La question est posée pour induire en erreur 

Tu cherches la réponse ou tu proposes l'exo? Je vois pas le rapport avec la géométrie par contre (à part qu'il y a la suite géométrique^^)

[Déplacé vers "arithmétique" --JLT]

gai requin

$u=0$

lesmathspointclaires

J'aurais dit pour tout $u$ mais j'ai peut-être mal lu l'enoncé^^

lesmathspointclaires

Car $u^n-n$ prend toutes les valeurs modulo $b$ pour tout $b$..  vu que $\phi(n) $ est premier avec $n$... Je dis peut-être nimp...?

Math Coss

Il n'est pas vrai que $\phi(n)$ et $n$ sont premiers entre eux en général, c'est même relativement rare – exemple : $93=3\times31$, $\phi(93)=3\times20$ ; pour $n>2$ pair, soit $4\mid n$, soit $n$ admet un diviseur premier impair et dans les deux cas, $\phi(n)$ est pair.

lesmathspointclaires

Haha oui, merci... et que dire des puissances de nombre premiers

lesmathspointclaires

"Il existe une infinité" équivaut à "il existe" (puisqu'on est modulo $b$)
Si $b$ est premier, comme $b$ et $\phi(b)$ sont premiers, on sent bien que les $u^n-n$ parcourent toutes les valeurs modulo $b$, prouvons que c'est aussi le cas général:
Soit $\nu=pgcd(b,\phi)$, où $\phi$ est l'ordre de $u$ dans les inversibles modulo $b$ 
 Pour tout entier $x\in [1,b/\nu]$,  $f(x,.)\space :$ $f_i(x)=i\mapsto (u^{x+i\phi}-x-i\phi)$ est injective de $[1,b/\phi]$ dans $\mathbb Z/b\mathbb Z$, puisque se factorisent suivant $u^{\phi}=1$, les différences deux à deux des images.

 On va montrer qu'il y a trop peu d'égalités du type  $f_1(n)=f_1 (m):=f(m)$ pour qu'on ne puisse pas tiroiraupigeonisé l'affaire. Puisque la dernière égalité concernant l'indexation en $1$ induit l'égalité sur tous les indices, il suffira de montrer que $card(f([1,\phi]))\geq \nu$. On note maintenant  $r$ le reste de la division euclidienne modulo $\phi$
La fonction $r_1\space :$ $[1,\phi/\nu].b \ni kb\mapsto r(kb)\in r.[1,\phi]$ étant bijective, on a cqfd.

Martin545445

Merci à tous d'avoir participé.

lesmathspointclaires

@Martin545445
Pas très sport d'avoir posté ta preuve avant que je termine la mienne🤣🤣, j'ai dû m'interrompre à un moment où je galerai avec les indices, mais c'était dejà plus ou moins plié à part les coquille, je pense pas que ça soit le cas mais même si je me suis trompé ce qui arrive souvent, tu peux quand même laisser finir, ça laisse entendre que c'est pas bon ce que j'ai mis, c'est peut-être le cas mais tu pourrais t'en assurer avant de placarder un pavé en anglais en plus eh l'autre hé^^ Parce que les gens lisent pas quand ils voient ça, et si celui qui poste la question ne lit même pas qui va le faire ? 

NB
Je vais un tout petit peu vite à certains endroits, mais je vais peaufiner (le passage avec f[1,phi] montrer qu'"on peut s'y ramener demande une petite discussion).
Je comprends aussi pourquoi tu l'as mise en géométrie d'une certaine façon, et y a un dessin je crois peut illustrer la preuve sans presque avoir besoin de l'écrire (j'exagère qu'un poil)

LOU16

Bonjour,

J'avais résolu le cas $b=p^r$ sans venir à bout du cas général. Voici donc "ma" solution partielle, qui utilise les mêmes ingrédients que celle reproduite par @Martin545445, mais qui me parait plus simple, et je l'espère, plus claire.

Soient $u,z\in \Z,\: b =p^r,\: p\text{ premier },r\in \N^*.\quad$ Notons: $\forall n \in\N,\:\: U_n=u^n-n-z.$

On prouve que: $\boxed{\mathcal E:=\Big\{ n\in\N\mid U_n\equiv 0 \mod b \Big\}\text{ est infini }.}$

$\bullet\:\: $ Si $\: p\text{ divise }u,\:$ alors $\:\forall n \in \N\text{ tel que }n\geqslant r\text{ et }n\equiv -z \mod b, \:\:U_n \equiv 0 \mod b.\quad \mathcal E \text{ est infini. }$

$\bullet\:\: $Si $\: u\wedge p =1,\:$ alors $u^{\varphi (b)} \equiv 1 \mod b,\: $entraîne que $u^{(p-1)p^r}\equiv 1 \mod b.$ 

Notons $p-1 =k.\: $ Alors $\: u^k =1 \mod p, \quad\boxed{ u^k =pa+1,\:a\in\Z, \:\:u^{kp^r}\equiv 1 \mod b.}$

Soient $x,y \in [\![0;b-1]\!] \text { distincts }, x>y.\quad $Ainsi $\quad x-y= lp^s,\:l\wedge p=1, \:0\leqslant s<r\:\: $

Montrons que $\:\:\boxed{U_{kx}\not\equiv U_{ky} \mod b.\:\:(\bigstar)}\quad $Par "l'absurde":

$U_{kx}\equiv U_{ky}\mod b \iff u^{ky}(u^{k(x-y)}-1)\equiv k(x-y) \mod b.\iff u^{ky}\left((pa+1)^{lp^s}-1\right) \equiv klp^s \mod p^r.$ 

 La $p-\text{valuation } $ du membre de droite de cette congruence est égale à $s$. Le lemme cité par @Martin545445 affirme que celle du membre de gauche est supérieure à $s+1.$Ainsi, cette congruence $\mod p^r$ est, à  cause de $s<r$, impossible. $\square$

$(\bigstar) $ exprime le fait que l'application $[\![0;b-1]\!]\to \Z/b\Z, \:x\mapsto U_{kx}\mod b\: $ est injective, et donc bijective.

$\exists m \in \N\text { tel que } U_{km}\equiv 0 \mod b.\:$ De plus: $\quad \forall n \in \N,\: U_{km+nkp^r}\equiv U_{km}\equiv 0 \mod b.$

$$\mathcal E \text{ est infini. }$$