Используя сравнения по модулю, найдите остатки от деления: а) 23n на 7 (для нечётных n) ( );

б) 612 ∙ 814 на 7 ( );

в) 2316 + 3316 + 4916 на 15 ( );

г) 31255 – 12553 на 8 ( ).

А) 2n; Б) 1; В) 8; Г) 3

Объяснение:

А) 23n : 7 для нечётных n = 2k+1

23(2k+1) = 46k + 23 = 42k + 4k + 21 + 2 = 4k + 2 (mod 7) = 2(2k+1) = 2n

Б) 6^12*8^14 = (6^2)^6 * (8^2)^7 = 36^6*64^7 = (35+1)^6*(63+1)^7 = 1^6*1^6 (mod 7) = 1

В) 23^16 + 33^16 + 49^16 = (23^2)^8 + (33^2)^8 + (49^2)^8 = 529^8 + 1089^8 + 2401^8 =

= (510+15+4)^8 + (1080+9)^8 + (2400+1)^8 = 4^8 + 9^8 + 1^8 (mod 15) =

= (4^2)^4 + (9^2)^4 + 1 = 16^4 + 81^4 + 1 = (15+1)^4 + (75+6)^4 + 1 = 1 + 6^4 + 1 (mod 15) =

= (6^2)^2 + 2 = 36^2 + 2 = (30+6)^2 + 2 = 6^2 + 2 (mod 15) = 36 + 2 = 38 = 8 (mod 15)

Г) 3^1255 - 1255^3 = (3^5)^251 - (1200+48+7)^3 = 243^251 - 7^3 (mod 8) =

= (240+3)^251 - 343 = 3^251 - (320+16+7) = 3*3^250 - 7 (mod 8) =

= 3*(3^5)^50 - 7 = 3*243^50 - 7 =

= 3*3^50 - 7 (mod 8) = 3*(3^5)^10 - 7 = 3*243^10 - 7 = 3*3^10 - 7 (mod 8) =

= 3*(3^5)^2 - 7 = 3*243^2 - 7 = 3*3^2 - 7 (mod 8) = 3*9 - 7 = 27 = (24+3) = 3 (mod 8)