Sigh, speravo di poter evitare, ma... here we go. Premessa: questo post è scritto di getto, e alla fine contiene dei commenti dei tipo "Ah, beh, ma in effetti sono un idiota, questi passaggi potevano essere evitati". Mentre lo leggi, cerca di vedere se noti dove si potrebbero accelerare i conti...
Cominciamo a calcolare potenze settime, per esempio. Abbiamo $1^7 \equiv 1$ e $2^7 \equiv 128 \equiv -1 \pmod{43}$. In particolare, si ha $4^7 \equiv 1 \pmod{43}$. E qui c'è una prima osservazione chiave per accelerare i conti: per ogni intero $a$ si ha $(4a)^7 \equiv 4^7 a^7 \equiv a^7 \pmod{43}$. Dunque, per esempio, i seguenti numeri hanno tutti la stessa potenza settima modulo 43: $1, 4, 16, 4^3 \equiv 21, 4^4 \equiv -2, 4^5 \equiv -8, 4^6 \equiv 11$ (in particolare, elevati alla settima fanno tutti 1).
D'altro canto, siccome $(-1)^7 = -1$, abbiamo che $-1, -4, -16, -21, 2, 8, -11$, quando elevati alla settima, danno $-1$.
E ora andiamo avanti: nelle due liste precedenti non compare 3, quindi calcoliamo $3^7 \equiv -6$. Chiaramente $-3$ alla settima darà $6$, e abbiamo già trovato 4 residui settimi ($\pm 1, \pm 6$). Ora fare $4^7$ non serve a niente (sappiamo già che fa 1), e $5^7$ non ci aiuta perché $5 \equiv 3 \cdot 4^2 \pmod{43}$. Anche $6^7 \equiv (-3)^{7 \cdot 7} \equiv (-3)^{49-\varphi(43)} = (-3)^7 \equiv 6$ non ci serve, e quindi proviamo $7^7 \equiv 7 \pmod {43}$. Questo è un residuo che non avevamo ancora visto, e chiaramente si ha anche $(-7)^7 \equiv -7 \pmod{43}$. Quindi $\{\pm 1, \pm 3, \pm 7\}$ sono residui settimi. D'altro canto, il numero di residui settimi non-zero è $\frac{43-1}{7}=6$, quindi li abbiamo trovati tutti.
Ok, questo non era troppo male, ma un pochino di tempo c'è voluto. Ora con le potenze seste usiamo un'altra idea e facciamo ancora meglio!
Certamente abbiamo $1^6 = 1$, $2^6 \equiv 4^3 \equiv 21$. Fermiamoci un istante a pensare: se $n$ è una potenza sesta, diciamo $n \equiv a^6 \pmod{43}$, chiaramente anche $n^2$, $n^3$ eccetera sono potenze seste (sono le potenze di $a^2, a^3,...$)! Allora forse posso essere più efficiente e calcolare $21^2, 21^3, ...$. Vediamo cosa succede. $21^2 \equiv 2^{12} \equiv 4^6 \equiv 11$, e il conto è gratis perché l'abbiamo già fatto prima. Ora $21^3 \equiv 2^{18} \equiv 4^9 \equiv 4^2 \equiv 16 \pmod{43}$, e questo è un nuovo residuo sesto! Ora $21^4 \equiv 2^{24} \equiv 4^{12} \equiv -8 \equiv 35 \pmod{43}$, anche questo è nuovo. E ancora $21^5 \equiv 4^{15} \equiv 4^7 \cdot 4^7 \cdot 4 \equiv 4 \pmod{43}$... yay! Ed infine $21^6 \equiv 21 \cdot 4 \equiv 84 \equiv -2 \pmod{43}$, che è ancora diverso. Ora mi fermo di nuovo un attimo a pensare: abbiamo già trovato $\{1,21,11,16,35,4,41\}$, che sono 7 classi di resto, e sappiamo che i residui sesti sono $\frac{43-1}{6}=7$, quindi abbiamo finito. E non mi puoi dire che sia stato un conto difficile: alla peggio abbiamo dovuto fare $84 \bmod 43$!
Ma in realtà è ancora meglio di quanto non sembri: sapevamo a priori che fare le potenze di $21$ avrebbe funzionato! Infatti, qual è l'ordine moltiplicativo di 21 modulo 43? Beh, sappiamo che $21=2^6$, quindi $21^7 \equiv 2^{42}\equiv 1 \pmod{43}$. Dunque l'ordine moltiplicativo di 21 divide 7, ma certamente non è 1, quindi è necessariamente proprio 7. Il che vuol dire che $21^1, 21^2, 21^3, 21^4, 21^5, 21^6, 21^7=1$ sono tutti diversi modulo 43. Ma siccome sono anche tutte potenze seste - l'abbiamo già visto - sono tutti e soli i residui sesti.
Ora i commenti del tipo "ma in realtà sono scemo". Nota che per trovare le potenze settime avremmo potuto essere più efficienti e - una volta trovato che $6$ è una potenza settima - avremmo potuto finire molto più velocemente calcolando $6^2 = 36 \equiv -7$. Ma a volte anche l'altra idea può essere utile!
Inoltre, se uno vuole ridurre veramente al minimo il numero dei conti da fare (e da scrivere in una gara...), una volta scoperto che 21 è una potenza sesta, con un minimo di ragionamento - ma bisognava fermarsi a pensare un po' di più - si sarebbe potuto osservare (l'avevate notato, miei attenti lettori?) che in effetti le potenze seste non sono altro che le potenze di 4, che avevamo già calcolato!
p.s. Naturalmente la risposta vera alla tua domanda è "con un computer"
. Ma fare il conto come qui sopra prende solo una manciata di minuti, soprattutto se lo fai con carta e penna e non scrivendo direttamente in LaTeX
...