Calcola quanto vale mod(37¹³,17), ovvero il resto di 37¹³ diviso per 17?

Proviamo a fare il calcolo a mano. Poi lo controlleremo con opportuni programmi.
Osservo che 37 = 17·2+3. Quindi 37¹³ = (17·2+3)¹³ diviso per 17 ha lo stesso resto di 3¹³ diviso per 17, ovvero
mod(37¹³,17) = mod(3¹³,17).
Osserviamo che mod(A·B, 17) = mod(A,17)·mod(B,17):
se A diviso 17 fa H con resto C (A=17·H+C) e B diviso 17 fa K con resto D (B=17·K+D), allora A·B = 17·(...)+C·D.
Quindi spezzo 3¹³ in un opportuno prodotto 3^...·3^...·...
3³ = 27 =(mod 17) 10; 3⁴ =(mod 17) 10·3 =(mod 17) 34-4 =(mod 17) -4; 3⁸ = 3⁴⁺⁴ =(mod 17) (-4)·:(-4) = 16 =(mod 17) −1.
Quindi:  mod(37¹³,17) = mod(3¹³,17) = mod(3⁸⁺⁴⁺¹,17) = (−1)·(−4)·3 = 12.
    Con R avrei ottenuto 12 sia calcolando mod(37^13,17) che mod(3^13,17). Il calcolo lo avrei effettuato usando il simbolo %%:  (3^13)%%17 = 12.  Con WolframAlpha basta battere mod(37^13,17).

    Per altri commenti: Strutture numeriche neGli Oggetti Matematici.