Resto della divisione (congruenza)

[socket]

Salve avrei dei dubbi nella risoluzione di questo esercizio:
\(\displaystyle 2961867515301112627340382741295402150813379531250000000000 = 2^{10}*3^{11}*5^{16}*7^{45} \)
Qual è il suo resto nella divisione per 13?
\(\displaystyle n=2^{10}*3^{11}*5^{16}*7^{45} \)
Naturalmente devo calcolare \(\displaystyle n \equiv x ( mod 13) \)
Non so come procedere :\

[Pappappero1]

Siccome le classi di resto rispettano la moltiplicazione (se sai cos'e' un anello \(\mathbb{Z}/n\mathbb{Z}\) e' un anello) ci basta calcolarci i resti di quelle potenze di primi. Vediamo cosa succede con $2^{10}$. Notiamo che $2^4 = 16$ ha resto $3$ $mod 13$, quindi in generale, se $4m + \alpha = n$ (con $\alpha = 0,1,2,3$), si ha che $2^n$ ha lo stesso resto di $3^m * 2^\alpha$. Vediamo ora cosa succede al $3$. $3^3 = 27$ ha resto $1$ modulo $13$. Quindi se $n = 3m + \alpha$ (questa volta con $\alpha = 0,1,2$) si ha che $3^n$ ha lo stesso resto di $3^\alpha$. Con questa tecnica puoi calcolare i resti per ognuna delle potenze. Poi puoi moltiplicarli tra loro e, dividendo di nuovo per $13$ ottenere il resto del numerone grande.