Moduli
Inviato: 04/09/2018, 15:12
${2^{10}}^{2018}$ $\equiv$ x (mod 10000)
Trovare x.
Che tecnica bisogna utilizzare qui?
Trovare x.
Che tecnica bisogna utilizzare qui?
Prova a spezzare la congruenza in un sistema con una modulo 16 e l'altra modulo 625. La prima vale 0 perché quella potenza è multipla di 2^4, la seconda vale 1 perché phi(625) = 500 e l'esponente 10^2018 ne è multiplo.
Ora ragioni su tutti i numeri della forma 625k+1 fino a 10000, osservi che modulo 16 fanno k+1, quindi k=15 e x=9376.