Упражнения для самостоятельной работы

141. По теореме Эйлера . При а = 3, т = 6 имеем: .

Так как (6) = 2, то 3 ² 1(mod 6), или 9 1(mod 6), Тогда, по лемме, (9 – 1) 6 или 8 6 (нацело!?). Где ошибка?

142. Докажите, что: а) 23 ¹⁰⁰ 1(mod 101); б) 81 ⁴⁰  1(mod100); в) 2 ⁷³  2 (mod 73).

143. Докажите, что а) 1¹⁶ + 3¹⁶ + 7¹⁶ + 9¹⁶  4 (mod 10);

б) 5 ^{4п + 1} + 7 ^{4п + 1} делится без остатка на 12..

144. Докажите теорему, обратную теореме Эйлера: если а ^{ (m)}  1(mod m), то (а, m) =1.

145. Найдите наименьший показатель степени kN, удовлетворяющий данному сравнению: а) ; б) ; в) ; г) ;

д) ; е) ; ж) ; з) .

и) ; к) ; л) ; м) .

146. Найдите остаток от деления:

а) 7¹⁰⁰ на 11; б) 9⁹⁰⁰ на 5; в) 5¹⁷⁶ на 7; г) 2¹⁹⁹⁹ на 5; д) 8³⁷⁷ на 5;

е) 26 ⁵⁷ на 35; ж) 35 ³⁵⁹ на 22; з) 5⁷¹⁸ на 103; и) 27²⁶⁰ на 40; к) 25¹⁹⁹⁸ на 62.

147*. Докажите, что а ⁵⁶¹  а (mod 11).

148*. Если каноническое разложение натурального числа п не содержит множителей 2 и 5, то 12-я степень этого числа оканчивается цифрой 1. Докажите.

149*. Докажите, что 2 ⁶⁴  16 (mod 360).

150*. Докажите: если (а, 65) =1 , (b, 65) =1, то a¹² – b¹² делится без остатка на 65.