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

[_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]

Qual'è questo problema?
proviene dal forum?

[_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]

Fine recupero.

[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

[Bruno]

...

D'accordissimo con te, Pietro
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

[Admin]

Davvero interessante Bruno!

Grazie del tuo contributo!

Ciao
Admin