Esercizio sulla potenza e modulo

[valerimartohan]

12365439^987345316 congruo ad a modulo 122, come si ricava la a?

[Quinzio]

Non so se questa e' la strada piu' veloce, comunque si puo' fare cosi':

$12365439 = 122 n_1 + 7 $

Quindi $ 12365439 ^ {n_2} = (122n_1 + 7)^{n_2} = 122 n_3 + 7^{n_2}$

Ora inizia a fare la lista dei resti di $7^{n_2} / 122$ tenendo traccia ovviamente solo del resto.
Si vede che si forma un ciclo di lunghezza 60, ovvero $7^{n_2} mod 122 = 7^{n_2 + 60} mod 122 $.
Lista dei resti:
[ot]7
49
99
83
93
41
43
57
33
109
31
95
55
19
11
77
51
113
59
47
85
107
17
119
101
97
69
117
87
121
115
73
23
39
29
81
79
65
89
13
91
27
67
103
111
45
71
9
63
75
37
15
105
3
21
25
53
5
35
1
Poi ricomincia il ciclo
7
49
99
...[/ot]

A questo punto si guarda l'esponente $987345316 = 60 n_4 + 16$.
$7^{60n_4 + 16} mod 122 = 7^16 mod 122$

Il 16imo resto della lista e' 77, quindi la soluzione del problema e' 77.

Salvo errori di calcolo.

[valerimartohan]

Grazie!

[valerimartohan]

Sarebbe stato possibile risolvere il problema con la formula phi di Eulero?

"Quinzio":Non so se questa e' la strada piu' veloce, comunque si puo' fare cosi':

$12365439 = 122 n_1 + 7 $

Quindi $ 12365439 ^ {n_2} = (122n_1 + 7)^{n_2} = 122 n_3 + 7^{n_2}$

Ora inizia a fare la lista dei resti di $7^{n_2} / 122$ tenendo traccia ovviamente solo del resto.
Si vede che si forma un ciclo di lunghezza 60, ovvero $7^{n_2} mod 122 = 7^{n_2 + 60} mod 122 $.
Lista dei resti:
[ot]7
49
99
83
93
41
43
57
33
109
31
95
55
19
11
77
51
113
59
47
85
107
17
119
101
97
69
117
87
121
115
73
23
39
29
81
79
65
89
13
91
27
67
103
111
45
71
9
63
75
37
15
105
3
21
25
53
5
35
1
Poi ricomincia il ciclo
7
49
99
...[/ot]

A questo punto si guarda l'esponente $987345316 = 60 n_4 + 16$.
$7^{60n_4 + 16} mod 122 = 7^16 mod 122$

Il 16imo resto della lista e' 77, quindi la soluzione del problema e' 77.

Salvo errori di calcolo.