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 »

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 »

Qual'è questo problema?
proviene dal forum?

_Luciano

Messaggio da _Luciano »

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: 869
Iscritto il: mer apr 20, 2005 3:47 pm
Località: Benevento

Messaggio da Admin »

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: 869
Iscritto il: mer apr 20, 2005 3:47 pm
Località: Benevento

Messaggio da Admin »

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 10
Livello 10
Messaggi: 2020
Iscritto il: lun nov 21, 2005 6:07 pm
Località: Bologna

Messaggio da Bruno »

...

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
(Bruno)

...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}

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

Messaggio da Admin »

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