Ultime cifre

[Rho33]

Dovrei avere trovato un modo abbastanza brutale e semplice che permette di calcolare le ultime $k$ cifre di un certo intero positivo $m$ di $n$ cifre. Prima di postarlo però, lo pongo come problema! A voi!

[burt]

sapendo cosa pero ? non so detto cosi mi sembra che non abbia proprio senso

[Rho33]

Non sapendo assolutamente nulla! Ti illustro cosa avevo pensato (è calcoloso ma efficace):

Calcolare le ultime $k$ cifre di un certo intero $m$ corrisponde a risolvere la congruenza $m \equiv x \pmod {10^k}$ che è univocamente determinata, per il Teorema Cinese del Resto, dalle due congruenze "spezzate" , ovvero :

$\displaystyle \left \{ {\begin{array}xm \equiv a \pmod {2^k} \\ m \equiv b \pmod {5^k}\end{array}} \right.$

Dove $a,b$ sono interi che si determinano solitamente con il teorema di Eulero e/o il FLT. In particolare il TCR ci garantisce che la soluzione sia unica. Allora si ottiene che, dalla prima posso scrivere:

$m=a+h \cdot 2^k$ con $h \in \mathbb{Z}$

Dalla seconda invece posso scrivere:

$m= b+ l \cdot 5^k$ con $l \in \mathbb{Z}$

Uguagliando le due equazioni, ricordando che $a,b$ sono noti, così come $k$ , si ottiene una semplice equazione diofantea lineare in due variabili:

$l \cdot 5^k-h \cdot 2^k=a-b$

Ora la soluzione generale $(l,h)$ di questa equazione sarà della forma:

$(t \cdot 2^k+ \alpha, t \cdot 5^k+ \beta) $ con $\alpha, \beta \in \mathbb{Z}$ interi fissati.

E sostituendo infine in una delle due equazioni iniziali si ottiene:

$m= b+ l \cdot 5^k \iff m=b+ (t \cdot 2^k+ \alpha) \cdot 5^k \iff m=b+ t \cdot 10^k + \alpha \cdot 5^k \iff m \equiv b+\alpha \cdot 5^k \pmod {10^k} $

Che ve ne pare?

[burt]

io non sono affatto bravo , non conosco il teorema cinese del resto e molto cose che hai citato , ma di una cosa sono sicuro .calcolare la ultime k cifre di un intero positivo m di n cifre non significa nulla , faccimo un esempio . se k = 5 ed n= 7 cifre calcolami queste ulime k cifre.. poi sulla correttezza dei passaggi matematici che hai fatto non ho dubbi , ma devi sapere qualcosa in piu su questo numero . se qualcuno bravo vuole intervenire mi fa piacere

[bern1-16-4-13]

Rho33 è partito dal presupposto che uno conosce di tale numero $n$ la classe di resto modulo $2^k$ e modulo $5^k$, e a questo punto ha applicato il teorema cinese del resto, che posso assicurarti non è nulla di trascendentale, seppur possa essere moolto utile in certi problemi: dato un sistema di congruenze della forma $$\begin{cases}x\equiv a_i\pmod{p_i^{\alpha_i}}\end{cases}$$dove i $p_i$ sono tutti primi distinti gli uni dagli altri, allora esistono (e sono infinite, ma tutte congrue tra loro modulo $\prod p_i^{\alpha_i}$) soluzioni di questo sistema.
Da notare però che il TCR garantisce l'esistenza di tali soluzioni, in quanto al modo di trovarle fornisce solo un algoritmo, che tuttavia può essere piuttosto lungo, nel nostro caso specialmente se $k$ è molto grande. Quindi direi che questo problema non ha molto senso, a meno che uno non si accontenti di esser sicuro dell'esistenza di soluzioni al sistema $$\begin{cases}x\equiv a\pmod{2^k}\\x\equiv b\pmod{5^k}\end{cases}$$