Using Fermat’s Little Theorem, show that 830 -1 is divisible by 31. 8 a] Using Fermat’s Little Theorem, show that 830 -1 is divisible by 31.
8^30 -1 is Divisible by 30 According to Fermat’s little theorem (1-p) ! 8²=64=2 mod 31 8⁴=4 mod 31 8^8 = 16 mod 31 8^16 = 8 mod 31 8^30=8^16 ×8^8×8⁴×8² = 8×16×4×2 = 1024 ~= 1 mod 31
8^30 -1 is Divisible by 30
According to Fermat’s little theorem
(1-p) !
8²=64=2 mod 31
8⁴=4 mod 31
8^8 = 16 mod 31
8^16 = 8 mod 31
8^30=8^16 ×8^8×8⁴×8²
= 8×16×4×2
= 1024 ~= 1 mod 31