Siano a e b interi maggiori di 1. Supponiamo che, per ogni n intero positivo primo con a, si ha che esiste x intero positivo tale che $ n|a^x-b $.
Si dimostri che esiste k intero positivo tale che $ a^k=b $
n|a^x-b
n|a^x-b
"Sei la Barbara della situazione!" (Tap)
Dunque... Deve esserci un v tale che $ \displaystyle~a^v-1>b\wedge v>0 $. Poniamo $ \displaystyle~n=a^v-1 $ (che possiamo fare, dato che $ \displaystyle~(a,a^v-1)=1 $). Deve esistere per ipotesi un x minimo tale che $ \displaystyle~a^v-1\mid a^x-b $. A meno che non sia $ \displaystyle~a^x-b=0 $, deve essere $ \displaystyle~v<x $, altrimenti si avrebbe $ \displaystyle~a^v-1\le a^x-b\le a^v-b\Rightarrow a^v-1\le a^v-b\Rightarrow b\le1 $. Possiamo quindi porre $ \displaystyle~y=x-v $. Abbiamo $ \displaystyle~a^{v+y}\equiv b\pmod{a^v-1}\Rightarrow a^y\equiv b\pmod{a^v-1}\Rightarrow a^v-1\mid a^y-b $, assurdo perché è $ \displaystyle~y=x-v<x $, avendo supposto x minimo. Quindi $ \displaystyle~a^x-b=0\Rightarrow a^x=b $.
P.S.: Dove hai preso questo problema?
P.S.: Dove hai preso questo problema?
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)
Il problema ha una storia particolare: cercavo di dimostrare la stessa tesi, ma con l'ipotesi che valeva solo per n primo. Mi serviva come lemma per risolvere un problema olimpico piuttosto difficile (cioè questo). Ho trovato la stessa tua dimostrazione e mi sono convinto che valesse anche per il lemma più forte e ho fatto una figura non troppo dignitosa su mathlinks...
Il mio ragionamento era: se esiste x tale che $ a^x\equiv b \pmod p $ per tutti i primi che dividono n, allora per il teorema cinese del resto (cioè prendendo un X che è congruente a x_p modulo p-1 per tutti i vari p) ho anche i numeri composti. Per passare invece dai primi alle potenze di primi non dovrebbe essere difficile...
Se vuoi divertirti trova l'errore...
Il mio ragionamento era: se esiste x tale che $ a^x\equiv b \pmod p $ per tutti i primi che dividono n, allora per il teorema cinese del resto (cioè prendendo un X che è congruente a x_p modulo p-1 per tutti i vari p) ho anche i numeri composti. Per passare invece dai primi alle potenze di primi non dovrebbe essere difficile...
Se vuoi divertirti trova l'errore...
"Sei la Barbara della situazione!" (Tap)
