Soluzione problema 19.jordan ha scritto:Problema 19.
Siano fissati degli interi positivi $ a,b,c $. Mostrare che esiste un intero positivo $ x $ tale che $ a^x+x \equiv b \pmod c $.
Lemma - $ \displaystyle~\forall n, m\in\mathbb{N}:m>0 $ la successione $ \displaystyle~\{n^i\}_{i>0} $ è periodica $ \displaystyle~\pmod m $ e il periodo divide $ \displaystyle~\phi\left(\frac{m}{(m,n)}\right) $.
Poniamo $ \displaystyle~v=\frac{m}{(m,n)} $. Chiaramente $ \displaystyle~n^{\phi(v)}\equiv1\pmod v $ (dato che $ \displaystyle~(n,v)=1 $). Abbiamo quindi $ \displaystyle~v\mid n^{\phi(v)}-1 $, da cui $ \displaystyle~m\mid (m,n)(n^{\phi(v)}-1) $ e a maggior ragione $ \displaystyle~m\mid n^x(n^{\phi(v)}-1)=n^{x+\phi(v)}-n^x,~\forall x>0 $. Ora con una somma telescopica (se non vi piace c'è anche l'induzione) si dimostra che $ \displaystyle~\forall x>0,0<x'\le\phi(v)~x\equiv x'\pmod{\phi(v)}\Rightarrow n^x\equiv n^{x'}\pmod m $, da cui la tesi.
Corollario - $ \displaystyle~\forall n, m\in\mathbb{N}:m>0 $ la successione $ \displaystyle~\{n^i\}_{i>0} $ è periodica $ \displaystyle~\pmod m $ e il periodo divide $ \displaystyle~\phi(m) $.
Ora ragioniamo per induzione estesa su c:
"Passo base" (
): Per $ \displaystyle~c=1 $ la tesi è ovvia. (In realtà per l'induzione questo caso è inutile)Passo induttivo: Vogliamo che esista un x che soddisfa $ \displaystyle~a^x+x\equiv b\pmod c $, oppure, ponendo $ \displaystyle~x=k\phi(c)+j,~0<j\le\phi(c) $, che $ \displaystyle~a^{k\phi(c)+j}+k\phi(c)+j\equiv b\pmod c $, cioè (per il lemma) $ \displaystyle~a^j+j\equiv -k\phi(c)+b\pmod c $.
Ora poniamo $ \displaystyle~m=(\phi(c),c) $ (da cui abbiamo che $ \displaystyle~m\le\phi(c)<c $) e $ \displaystyle~\phi(c)=rm $ (quindi $ \displaystyle~\left(r,\frac{c}{m}\right)=1 $). Rimane da dimostrare che per qualche $ \displaystyle~(k,j) $ si ha $ \displaystyle~a^j+j\equiv -krm+b\pmod c $.
Caso $ \displaystyle~m>1 $: Per l'ipotesi induttiva abbiamo che $ \displaystyle~\exists j:a^j+j\equiv b\pmod m $ e possiamo supporre $ \displaystyle~0<j\le\phi(c) $ (che non lede la generalità della tesi dato che $ \displaystyle~m\mid\phi(c)\wedge\phi(m)\mid\phi(c) $). Per qualche s abbiamo cioè $ \displaystyle~a^j+j=ms+b $. Rimane da provare che per qualche k $ \displaystyle~ms+b\equiv -krm+b\pmod c $, ovvero $ \displaystyle~mkr\equiv -ms\pmod c $. Questa ultima equivalenza si riduce a $ \displaystyle~kr\equiv -s\pmod{\frac{c}{m}} $. Dato che $ \displaystyle~\left(r,\frac{c}{m}\right)=1 $, possiamo ricavare direttamente k: $ \displaystyle~k\equiv -sr^{-1}\pmod{\frac{c}{m}} $. L'esistenza di k è dimostrata dato che gli ultimi passaggi sono invertibili.
Caso $ \displaystyle~m=1 $: Per un j a scelta si ricava direttamente k: $ \displaystyle~k\equiv(a^j+j-b)r^{-1} $.
Di conseguenza esiste anche un x che rispetta la tesi. Fatemi sapere...
così ne ho approfittato 
)
..........