n|a^x-b

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

n|a^x-b

Messaggio da piever » 22 mar 2009, 14:37

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 $
"Sei la Barbara della situazione!" (Tap)

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 29 mar 2009, 16:51

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?
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 29 mar 2009, 20:02

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...
"Sei la Barbara della situazione!" (Tap)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 29 mar 2009, 23:57

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 :roll:
The only goal of science is the honor of the human spirit.

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 30 mar 2009, 11:13

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 :roll:
Eggià, come è noto i vari (p-1) sono primi tra loro... :oops:
"Sei la Barbara della situazione!" (Tap)

Rispondi