5.8. Теореми Ейлера і Ферма. Китайська теорема про остачи. Переведення чисел із позиційної системи числення у систему лишкових класів та навпаки

Номери ваших індивідуальних завдань обчислюються за формулою (А + 25k)(mod 116), k = 0  5, де A  порядковий № за журналом,  порядковий номер навчальної групи. Вибираються номери записані нежирним шрифтом.

Зміст задач та завдань

8.5. Чи справджується теорема Ейлера для таких чисел:

5.8.1. а) a = 2, m = 9; е) a = 4, m = 9;

5.8.2. б) a = 2, m = 15; 5.8.6. є) a = 5, m = 24;

5.8.3. в) a = 3, m = 4; 5.8.7. ж) a = 2, m = 38;

5.8.4. г) a = 3, m = 9; 5.8.8. з) a = 3, m = 24?

5.8.5. д) a = 3, m = 16;

8.2. Чи справджується мала теорема Ферма для таких чисел:

5.8.9. а) a = 2, p = 3; 5.8.14. е) a = 5, p = 3;

5.8.10. б) a = 2, p = 5; 5.8.15. є) a = 5, p = 7;

5.8.11. в) a = 3, p = 2; 5.8.16. ж) a = 4, p = 3;

5.8.12. г) a = 10, p = 5; 5.8.17. з) a = 4, p = 5;

5.8.13. д) a = 5, p = 2; 5.8.18. к) a = 14, p = 7?

8.3. Користуючись теоремою Ейлера, знайти остачу від ділення:

5.8.19. а) 7⁶⁷ на 12; 5.8.24. е) 293²⁷⁵ на 48;

5.8.20. б) 109³⁴⁵ на 14; 5.8.25. є) 439²⁹¹ на 60;

5.8.21. в) 197¹⁵⁷ на 35; 5.8.26. ж) 527¹⁴⁴ на 65;

5.8.22. г) 356²⁷³ на 39; 5.8.27. з) 353¹⁶⁰ на 75;

5.8.23. д) 383¹⁷⁵на 45; 5.8.28. к) 485⁸⁴ на 129.

8.4. Користуючись малою теоремою Ферма, знайти остачу від ділення:

5.8.29. а) 93²⁵³ на 7; 5.8.33. д) 2598³³ на 17;

5.8.30. б) 5008¹⁰⁰⁰⁰ на 5, 7, 11, 13; 5.8.34. е) 230³⁷ на 37;

5.8.31. в) 42⁵⁰ на 17; 5.8.35. є) 71⁵⁰ на 67;

5.8.32. г) 20⁵⁹ на 17; 5.8.36. ж) 512⁴⁰² на 105.

8.5. Знайти остачу від ділення:

5.8.37. а) 45⁸³ на 24; 5.8.40. г) 204⁴¹ на 111;

5.8.38. б) 6⁷⁶ на 26; 5.8.41. д) 460¹⁵⁰ на 425.

5.8.39. в) 96¹¹³ на 92;

8.6. Знайти остачу від ділення:

5.8.42. а) 7¹⁰⁰ + 8¹⁰⁰ на 5; 5.8.47. е) 15⁶⁰ + 20³⁰ на 13;

5.8.43. б) 10¹⁰⁰ + 40¹⁰⁰ на 7; 5.8.48. є) 5⁷⁰ + 7⁵⁰ на 12;

5.8.44. в) 3¹⁰⁰ + 4¹⁰⁰ на 7; 5.8.49. ж) 3⁵⁰⁰ + 7⁵⁰⁰ на 101;

5.8.45. г) 5⁵⁰ + 25⁷⁰ на 9; 5.8.50. з) (12371⁵⁶ + 145)²⁸ на 111;

5.8.46. д) 25⁸⁰ + 40⁸⁰ на 11; 5.8.51. к) 3´5⁷⁵ + 4´7¹⁰⁰ на 132.

8.7. Знайти дві останні цифри числа:

5.8.52. а) 3¹⁰⁰; 5.8.56. д) 17⁹⁰⁰; 5.8.60. з) 2¹⁰⁰;

5.8.53. б) 3²¹⁹; 5.8.57. е) 19⁸⁸²; 5.8.61. к) 2¹⁵³;

5.8.54. в) 11²⁴³; 5.8.58. є) 903¹²⁹⁴; 5.8.62. л) 102⁵⁴.

5.8.55. г) 13²¹⁹; 5.8.59. ж) 573¹⁹³¹;

8.8. Знайти остачу вiд дiлення, застосувуючи якщо можна теореми Ейлера або Ферма.

5.8.63. а) 15²³¹ на 14;

5.8.64. б) 15²³¹ + 2 на 16;

5.8.65. в) 1532⁵ 1 на 9;

5.8.66. г) 12¹²³¹ + 14⁴³²⁴ на 13;

5.8.67. д) 208²⁰⁸ на 23;

5.8.68. е) 2¹⁵⁷⁸³ 7 на 25;

5.8.69. э) 3⁷⁹⁸²¹ + 5 на 17;

5.8.70. ж) 10²⁷³² + 10 на 22;

5.8.71. з) 18²⁸¹⁵ 3 на 14;

5.8.72. к) 2¹⁰⁰ + 5²⁰⁰ на 29;

5.8.73. л) 13¹⁰⁵⁴ 2316²⁸⁵ + 22¹⁷ на 15;

5.8.74. м) 29²⁹²⁹34³⁴³⁴ + 29416²³¹ – 2417¹²⁰ на 31;

5.8.75. н) а на 73, якщо а¹⁰⁰  2 (mod 73) i a¹⁰¹  69 (mod 73). Як змiниться вiдповiдь, якщо а подiлити на 79 i а²⁵  3 (mod 79), а²⁶  29 (mod 79), (a,79) = 1?

8.8. Знайти останнi двi цифри чисел, застосувуючи якщо можна теореми Ейлера або Ферма.

5.8.76. a) 2⁹⁹⁹; 5.8.80. д) 203²⁰³²⁰³;

5.8.77. б) 3⁹⁹⁹; 5.8.81. e) ;

5.8.78. в) 2³⁴¹; 5.8.82. є) ;

5.8.79. г) 289²⁸⁹; 5.8.83. ж) .

8.9. Довести, що (для пунктів а), б), в), д) скористатися китайською теоремой про остачи):

5.8.84. а)

5.8.85. б)

5.8.86. в)

5.8.87. г)

5.8.88. д)

8.10. Довести, що:

5.8.89. а)

5.8.90. б)

5.8.91. в)

5.8.92. г)

5.8.93. д)

5.8.94. е)

5.8.95. є)

5.8.96. ж)

5.8.97. з)

5.8.98. к) , .

11. Нехай просте число. Довести, що:

5.8.99. а) , якщо ;

5.8.100. б) або , якщо , ;

5.8.101. в) і , якщо , ;

5.8.102. г) ;

5.8.103. д) , якщо ;

5.8.104. е) , якщо просте число і ;

5.8.105. є) є простим числом, якщо ;

5.8.106. ж) , якщо ;

5.8.107. з) є складеним числом, якщо , а просте число;

5.8.108. к) , якщо просте число, і .

12. Знайти остачу від ділення:

5.8.109. а) на 125, ;

5.8.110. б) на число m, якщо воно не парне і ;

5.8.111. в) на число m, якщо воно не парне і ;

13. а) Довести, що:

5.8.112. а) , якщо , і ;

5.8.113. б) , якщо , ;

5.8.114. в) , якщо ;

5.8.115. г) толі і тільки тоді, коли , ;

5.8.116. д) , якщо a є кубом деякого цілого числа.