Ciao a tutti!
Come calcolare il resto di 3^2048 diviso 2^14?
E soprattutto dove cercare una trattazione completa di aritmetica modulare?
Calcolo resto
Ciao edo, benvenuto nel forum!
Voglio farti notare che c'è una sezione apposita per le domande di teoria e nel caso ti vorresti presentare c'è anche questa.
Ad ogni modo, hai postato quest'esercizio oggi pomeriggio, strano che nessuno ti abbia ancora risposto o non sia passato HarryPotter nei paraggi..
Comunque per la tua domanda credo che questa dispensa sia più che sufficiente.
Per il tuo problema:
Lemma. Dato un intero dispari $ a \in 2\mathbb{Z}+1 $ e un intero positivo $ n \in\mathbb{N}_0 $ valgono le seguenti:
i) $ \displaystyle 2^{n+3}|a^{(2^n)}-1 $ se $ 16|a^2-1 $.
ii) $ \displaystyle 2^{n+3}|a^{(2^n)}-2^{n+2}-1 $ altrimenti.
Prova. L'ipotesi $ 16|a^2-1 $ equivale a $ a \equiv \pm 1 \pmod{8} $. Se $ n=1 $ la tesi è verificata, infatti $ 1^2 \equiv 7^2 \equiv 1 \pmod{16} $ e $ 3^2 \equiv 5^2 \equiv 9 \pmod{16} $. Supponiamo che la tesi sia verificata per $ n \in \mathbb{N}_0 $, e mostriamo che è valida anche per $ n+1 $ (per la cronaca tale procedimento è la PMI). Se $ 16|a^2-1 $ allora abbiamo per ipotesi che $ \displaystyle 2^{n+3}|a^{(2^n)}-1 $, allora esiste $ k \in \mathbb{N} $ tale che $ a^{(2^n)}=k2^{n+3}+1 $. Ma $ a^{(2^{n+1})}=(a^{2^n})^2=(k2^{n+3}+1)^2 \equiv 1 \pmod{2^{n+4}} $, che è la tesi. Nell'altro caso, cioè se $ 8|a-3 $ oppure $ 8|a-5 $ se la tesi vale per $ n \in \mathbb{N} $ allora vale anche per $ n+1 $, infatti per ipotesi avremo che esiste un $ t \in\mathbb{N} $ tale che $ a^{(2^n)}=t2^{n+3}-2^{n+2}-1 $ e quindi $ a^{(2^{n+1})}=(t2^{n+3}-2^{n+2}-1)^2 \equiv (2^{n+2}+1)^2 \equiv 2^{n+3}+1 \pmod{2^{n+4}} $, che conclude la prova.
Corollario. Dato un intero dispari $ a \in 2\mathbb{Z}+1 $ e un intero positivo $ n \in\mathbb{N}_0 $ vale la seguente:
iii) $ \displaystyle 2^{n+2}|a^{(2^n)}-1 $.
Soluzione. Per il lemma sopra, posto $ n=11 $ vale: $ \displaystyle 3^{(2^{11})} \equiv 2^{13}+1 \pmod{2^{14}} $.
Saluti
Voglio farti notare che c'è una sezione apposita per le domande di teoria e nel caso ti vorresti presentare c'è anche questa.
Ad ogni modo, hai postato quest'esercizio oggi pomeriggio, strano che nessuno ti abbia ancora risposto o non sia passato HarryPotter nei paraggi..
Comunque per la tua domanda credo che questa dispensa sia più che sufficiente.
Per il tuo problema:
Lemma. Dato un intero dispari $ a \in 2\mathbb{Z}+1 $ e un intero positivo $ n \in\mathbb{N}_0 $ valgono le seguenti:
i) $ \displaystyle 2^{n+3}|a^{(2^n)}-1 $ se $ 16|a^2-1 $.
ii) $ \displaystyle 2^{n+3}|a^{(2^n)}-2^{n+2}-1 $ altrimenti.
Prova. L'ipotesi $ 16|a^2-1 $ equivale a $ a \equiv \pm 1 \pmod{8} $. Se $ n=1 $ la tesi è verificata, infatti $ 1^2 \equiv 7^2 \equiv 1 \pmod{16} $ e $ 3^2 \equiv 5^2 \equiv 9 \pmod{16} $. Supponiamo che la tesi sia verificata per $ n \in \mathbb{N}_0 $, e mostriamo che è valida anche per $ n+1 $ (per la cronaca tale procedimento è la PMI). Se $ 16|a^2-1 $ allora abbiamo per ipotesi che $ \displaystyle 2^{n+3}|a^{(2^n)}-1 $, allora esiste $ k \in \mathbb{N} $ tale che $ a^{(2^n)}=k2^{n+3}+1 $. Ma $ a^{(2^{n+1})}=(a^{2^n})^2=(k2^{n+3}+1)^2 \equiv 1 \pmod{2^{n+4}} $, che è la tesi. Nell'altro caso, cioè se $ 8|a-3 $ oppure $ 8|a-5 $ se la tesi vale per $ n \in \mathbb{N} $ allora vale anche per $ n+1 $, infatti per ipotesi avremo che esiste un $ t \in\mathbb{N} $ tale che $ a^{(2^n)}=t2^{n+3}-2^{n+2}-1 $ e quindi $ a^{(2^{n+1})}=(t2^{n+3}-2^{n+2}-1)^2 \equiv (2^{n+2}+1)^2 \equiv 2^{n+3}+1 \pmod{2^{n+4}} $, che conclude la prova.
Corollario. Dato un intero dispari $ a \in 2\mathbb{Z}+1 $ e un intero positivo $ n \in\mathbb{N}_0 $ vale la seguente:
iii) $ \displaystyle 2^{n+2}|a^{(2^n)}-1 $.
Soluzione. Per il lemma sopra, posto $ n=11 $ vale: $ \displaystyle 3^{(2^{11})} \equiv 2^{13}+1 \pmod{2^{14}} $.
Saluti
The only goal of science is the honor of the human spirit.