98 ! для 5-7 классов. решить в две строчки!
заранее решившему!
а). если целые числа a и m взаимно-просты, то найдется такое натуральное n, что аⁿ - 1 делится на m. докажите это.
б). также нужно определить, существует ли число вида , которое делится на 97. ответ, кажется, положительный.
Ответы на вопрос:
(а)
показателем числа a по модулю m (где a и m взаимно простые) называется наименьшее натуральное число n такое, что aⁿ - 1 делится на m (точнее aⁿ ≡ 1 (mod
докажем, что у взаимно простых чисел a и m существует показатель. действительно, пусть его не существует. тогда есть такие различные числа p и q, что a^p ≡ t (mod m) и a^q ≡ t (mod m). пусть p < q, тогда a^q : a^p ≡ t : t ≡ 1 (mod m). деление возможно из-за взаимной простоты a и m. значит, a^(q-p) ≡ 1 (mod m) и показатель существует.
(б)
заметим, что 100 ≡ 3 (mod 97), из этого:
100² ≡ 3 * 100¹ ≡ 3 * 3¹ ≡ 3² (mod 97)
100ⁿ ≡ 3 * 100^(n-1) ≡ 3 * 3^(n-1) ≡ 3ⁿ (mod 97)
кроме того известно, что 3⁰ + 3¹ + + 3ⁿ = (3^(n+1) - 1)/2 (это доказывается при метода индукции, при желании могу приложить доказательство в комментариях).
наше число представимо в виде 100⁰ * 19 + 100¹ * 19 + + 100ⁿ * 19 ≡ 3⁰ * 19 + 3¹ * 19 + + 3ⁿ * 19 ≡ (3^(n+1) - 1)/2 * 19 (mod 97).
так как 19 и 2 взаимно просты с 97, можно их убрать. если число 3^(n+1)-1 не делилось на 97, то и при умножении на них делиться не будет.
а теперь заметим, что существует такое n, что 3^(n + 1) - 1 делится на 97 (по первой ).
ответ: существует.
Популярно: Математика
-
milashka45528.06.2022 07:25
-
kirillefimov115.01.2023 23:42
-
Мур695409.06.2021 21:10
-
kari201830.03.2021 03:03
-
АринаВарданян06.09.2020 07:08
-
romanovegorka610.08.2022 06:38
-
камила50830.08.2021 03:16
-
DashaZakh15.12.2022 10:43
-
Aurusu11.10.2021 16:09
-
кек90317.05.2023 12:08