Congruenze modulo n e resto della divisione

[chri962008]

Ciao a tutti, sono nuovo in questo Forum, sto cercando di risolvere questo esercizio di matematica discreta:

Dato il numero:
$ 2961867515301112627340382741295402150813379531250000000000 = 2^10 * 3^11 * 5^16 * 7^45 $

- determinare il suo resto nella divisione per 13.

Ho capito che è necessario studiare $ (2^10 * 3^11 * 5^16 * 7^45)mod(13) $
ma non riesco a capire se studiando le varie potenze singolarmente bisogna applicare il teorema di Fermat o la funzione di Eulero

Grazie a chi potrà aiutarmi!!

[fmnq]

E' chiaro che basta calcolare le potenze di 2, 3, 5 e 7 modulo 13 separatamente, e poi moltiplicarle e ridurle. $2^{10}=1024=78\times 13+10$, sicché \(2^{10}\pmod{13}=10\). Allo stesso risultato arrivi applicando il piccolo teorema di Fermat, che dice che \(2^{12}\pmod{13}=1\), e che quindi \(2^{10}= 2^{-2} = (2^{-1})^2\).

Fai la stessa cosa con 3, con 5 e con 7.

[chri962008]

Grazie mille per la risposta così rapida!!

ho provato come hai detto tu:

$ 2^10 = 1024-= 10(mod 13) $
$ 3^11 = 177147-= 9(mod 13) $
$ 5^16 = 5^12 * 5^4 -= 1^12 * 5^4 -= 1(mod 13) $
$ 7^45 = (7^12)^3 * 7^9 -= 1^3 * 7^9 -= 8(mod 13) $

fatto ciò ho moltiplicato ed ho ottenuto

$ (10*9*1*8)-= 5(mod 13) $

il resto, dunque, è 5
è corretto??

[otta96]

Il risultato è giusto, comunque potevo fare anche in altri modi per esempio notare che $7^(-1)=2\mod13$ perché $2*7=13+1$ e $5^2=-1\mod13$ perché $5^2=2^13-1$ e che $3^(-1)=9\mod13$ perché $3*9=2*13+1$, quindi per il piccolo teorema di Fermat e quanto detto si ha: $2^10*3^11*5^16*7^45=2^10*3^11*5^4*7^9\mod13=2^10*3^(-1)*(5^2)^2*2^(-9)\mod13=2*9*(-1)^2\mod13=18\mod13=5\mod13$