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

_Edmund · 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?

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

Fine recupero.

Messaggio da **Admin** » dom set 03, 2006 7: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

Bruno · Messaggio da **Bruno** » lun set 04, 2006 6:16 pm

...

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

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

Davvero interessante Bruno!

Grazie del tuo contributo!

Ciao
Admin