Модульное сокращение математики до остаточного модуля

Question

Мне нужна помощь по модулю. Я видел этот пример в своей книге и не понимаю, как мой проф получил его. Может ли кто-нибудь объяснить мне, как это работает?

2^345 = (2^5)^69 = 32^69 = 1^69 = 1 (Mod 31)

В = знаки являются конгруэнтно знаки.

Answer 1

Только третий знак должен быть конгруэнцией, фактически: 2^345 = (2^5)^69 (поскольку n^(a * b) == (n^a)^b); 2^5, конечно, 32; и 1^п = 1 для всех п.

Итак, почему 32^69 ~ = 1^69 (используя ~ = как «конгруэнтно»)?

Простой.

32 ~= 1 mod (31) => 
32 = (n*31)+1 => 
32^p = ((n*31)+1)^p 
    = (n*31)^p + a*1*(n*31)^(p-1) + b*(1^2)*(n*31)^(p-1) + ... + 1^p for some a,b... 
    = (n*31)*z + 1 for some z 
    ~= 1 (mod 31) 

В целом, поэтому, если a ~= b (mod p) затем a^n ~= b^n (mod p)