Pagina 1 di 1
n|a^x-b
Inviato: 22 mar 2009, 14:37
da piever
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 $
Inviato: 29 mar 2009, 16:51
da kn
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?
Inviato: 29 mar 2009, 20:02
da piever
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...
Inviato: 29 mar 2009, 23:57
da jordan
piever ha scritto:...allora per il teorema cinese del resto (cioè prendendo un X che è congruente a x_p modulo p-1 per tutti i vari p)[...]
Mmmmm
Inviato: 30 mar 2009, 11:13
da piever
jordan ha scritto:piever ha scritto:...allora per il teorema cinese del resto (cioè prendendo un X che è congruente a x_p modulo p-1 per tutti i vari p)[...]
Mmmmm
Eggià, come è noto i vari (p-1) sono primi tra loro...
