R: "il principio dei cassetti" - 14. Cifre terminali

Forum dedicato ai quesiti irrisolti presenti nella collezione di Base5, nel vecchio forum ed in quello attuale.

Moderatori: Gianfranco, Bruno

Rispondi
_Edmund

R: "il principio dei cassetti" - 14. Cifre terminali

Messaggio da _Edmund » lun feb 06, 2006 7:28 pm

14. Cifre terminali

Esiste una potenza di 3 che termina per 001?


soluz.


la più piccola è 3^100:

3^100 = 515377520732011331036461129765621272702107522001

in generale sono del tipo 3^(n*100) con "n" numero naturale
in quanto qualunque potenza di 3^100 terminerà sempre per 001

_Admin

Messaggio da _Admin » lun feb 06, 2006 7:28 pm

Qual'è questo problema?
proviene dal forum?

_Luciano

Messaggio da _Luciano » lun feb 06, 2006 7:31 pm

Come, da dove proviene?

Pietro, proviene dai quesiti irrisolti:
COMBINATORIA

Dalla sezione "il principio dei cassetti"

14. Cifre terminali

Esiste una potenza di 3 che termina per 001?

Admin
Amministratore del sito
Amministratore del sito
Messaggi: 778
Iscritto il: mer apr 20, 2005 2:47 pm
Località: Benevento

Messaggio da Admin » lun feb 06, 2006 8:18 pm

Fine recupero.
Pietro Vitelli (Amministratore del Forum)
"Un matematico è una macchina che converte caffè in teoremi" Paul Erdös
www.pvitelli.net

Admin
Amministratore del sito
Amministratore del sito
Messaggi: 778
Iscritto il: mer apr 20, 2005 2:47 pm
Località: Benevento

Messaggio da Admin » dom set 03, 2006 6:46 pm

Volevo dimostrare la risposta di Edmund:

consideriamo la generica potenza di 3, 3^x;
deve essere

3^x \equiv 1\,\pmod{1000}

ora sappiamo che 3^4=81 termina per 1 e quindi anche 3^{\small{4^n}}=3^{4n} terminerà per 1.

Qundi affinche 3^x termini per 1, x deve essere multiplo di 4, ossia x=4n.

Qundi deve essere

3^{4n} \equiv 1\,\pmod{1000}\quad\Rightarrow\quad(81)^n \equiv 1\,\pmod{1000}

possiamo scrivere 81^n come:

(80+1)^n=80^n+{n \choose 1}80^{n-1}+{n \choose 2}80^{n-2}+\cdot\cdot\cdot+{n \choose \small{n-2}}80^2+{n \choose \small{n-1}}80+1

l'1 finale ci da la cifra delle unità;
il termine {n \choose \small{n-1}}80 determina la cifra delle decine che deve essere 0;
e il termine {n \choose \small{n-2}}80^2+{n \choose \small{n-1}}80 determina la cifra delle centinaia che deve essere anch'essa 0;

per cui deve essere
  • {n \choose \small{n-1}}80 \equiv 0\,\pmod{ 100}\quad\Rightarrow\quad 4n \equiv 0\,\pmod5
    Quindi n deve essere multiplo di 5, ossia n=5k
  • {n \choose \small{n-2}}80^2+{n \choose \small{n-1}}80\equiv 0\,\pmod{ 1000}\quad\Rightarrow\quad \frac{n^2-n}{2}\cdot80^2+80n\equiv 0\,\pmod{ 1000}
    dividendo per 40:
    (n^2-n)\cdot80+2n\equiv 0\,\pmod{ 25}\quad\Rightarrow\quad 80n^2-78n\equiv 0\,\pmod{ 25}
    abbiamo ricavato però che n=5k, per cui sostituendo si ha:
    80\cdot25k^2-78\cdot5k\equiv 0\,\pmod{ 25}
    dividendo per 5:
    400k^2-78k\equiv 0\,\pmod{ 5}
    affinchè la congruenza sia verificata, essendo 400k^2 divisibile per 25, c'è bisogno che lo sia anche 78k, ossia:
    78k \equiv 0\,\pmod5
    quindi k deve essere multiplo di 5, ossia k=5c;
    quindi n=5k=25c; ossia n deve essere multiplo di 25.
Quindi x=4n=100c, ossia x deve essere multiplo di 100.

Admin
Pietro Vitelli (Amministratore del Forum)
"Un matematico è una macchina che converte caffè in teoremi" Paul Erdös
www.pvitelli.net

Bruno
Livello 8
Livello 8
Messaggi: 997
Iscritto il: lun nov 21, 2005 6:07 pm
Località: Bologna

Messaggio da Bruno » lun set 04, 2006 5:16 pm

...

D'accordissimo con te, Pietro :D
Seguendo i tuoi stessi spunti, mi sono chiesto se
sia possibile avere, al tempo stesso:

3^{\script 100} \equiv 1 \;\pmod 8 \\ 3^{\script 100} \equiv 1 \;\pmod {125}.

In effetti, salvo sviste, mi sembra proprio così.
Infatti:

3^{\script 100} = (2+1)^{\script 100} = 8\cdot h+\frac{99\cdot 100}{2}\cdot2^{\script 2}+100\cdot 2+1 = 8\cdot k+1

per certi h e k. E poi:

3^{\script 100} = (5-2)^{\script 100} = 125\cdot p+\frac{99\cdot 100}{2}\cdot 5^{\script 2}\cdot 2^{\script 98}\,-100\cdot 5\cdot 2^{\script 99}+2^{\script 100} = 125\cdot q+2^{\script 100}

per certi p e q.

Ora, sappiamo che \,2^{\script 7}=128=125+3, quindi:

3^{\script 100} \equiv 2^{\script 100} \equiv 3^{\script 14}\cdot 4 = 19131876 = 125\cdot 153055 +1 \equiv 1 \; \pmod {125}.

Per un teorema delle congruenze, essendo \,(8,\,125)=1,
possiamo dire che:

3^{\script 100} \equiv 1 \; \pmod {8\cdot 125}

e, infine:

3^{\script 100n} \equiv 1 \; \pmod {1000}

per ogni intero n non negativo.

Con questo abbiamo risposto alla domanda iniziale e
cioè abbiamo dimostrato che esistono infinite potenze
di 3 terminanti con 001.

Ciao e a presto!


Bruno
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
(Biagio Marin)

Admin
Amministratore del sito
Amministratore del sito
Messaggi: 778
Iscritto il: mer apr 20, 2005 2:47 pm
Località: Benevento

Messaggio da Admin » mar set 05, 2006 1:53 pm

Davvero interessante Bruno! :)

Grazie del tuo contributo!

Ciao
Admin
Pietro Vitelli (Amministratore del Forum)
"Un matematico è una macchina che converte caffè in teoremi" Paul Erdös
www.pvitelli.net

Rispondi