Модулярлық арифметикада кері шамаларды есептеу туралы қазақша реферат
Нақты сандарды арифметикада а-1 мультипликативтi керi шаманы есептеу қиынға түспейдi. Нөлдiк емес а үшiн: a-1 = немесе а*а-1 = 1 деп есептейміз.
Мысалы, мультипликативтi керi шама 4 санынан ¼-ке тең, өйткенi 4* = 1-ге тең болғандықтан.
Ал модулярлық арифметикада керi шаманы есептеу қиын есеп болып табылады. Мысалы, салыстыруды есептеу 4*x ≡ 1 (mod 7) х және к мәндерiн табумен эквиваленттi, бұл 4*х ≡ 7*к + 1-ге тең, мұндағы х және к — бүтiн сандар.
Бұл есептiң жалпы тұжырымы – х бүтiн санын табу, бұл дегенiмiз a*x (mod n) = 1, басқаша осылай a-1 ≡ x (mod n) деп жазуға болады.
Бұл есептiң шешiмi кейде болады, кейде болмайды. Мысалы, 14 модулi бойынша 5 саны үшiн керi шама 3-ке тең, өйткенi
5*3 = 15 ≡ 1 (mod 14)
Келесi жақтан қарасақ, 14 модулi бойынша 2 санында керi шама жоқ.
Егер а және n — өзара жай сандар болса, жалпы a-1 ≡ x (mod n) салыстыруында бiр ғана нәтиже бар,.
Егер а және n сандары өзара жай сандар болмаса, онда салыстыру a-1 ≡ x (mod n) тең болады.
Нәтижесi жоқ керi шаманы табудың негiзгi әдiсiн тұжырымдаймыз. a {0, 1, 2, …, n-1} бүтiн сандар болсын. Егер ЕҮОБ(a, n) = 1, онда a*i (mod n), мұндағы i = 0, 1, 2, …, n-1, {0, 1, 2, …, n — 1}жиынтығын алмастыру болып табылады.
Мысалы, егер a = 3 және n = 7 (ЕҮОБ(3, 7) = 1), онда 3*i (mod 7), мұндағы i = 0, 1, 2, …, n-1; 0, 3, 6, 2, 5, 1, 4 жүйелiк болып табылады., яғни {0, 1, 2, …, 6}жиынтығын алмастыру болып табылады.
Егер ЕҮОБ(a, n) ≠ 1 болса, жоғарыда келтірілген мысал дұрыс емес болып шығады. Мысалы, егер a = 2 және n = 6 болса, онда 2*i (mod 6) ≡ 0, 2, 4, 0, 2, 4 мұндағы i = 0, 1, 2, …, 5 болады.
Егер ЕҮОБ(a, n) = 1, онда a-1 керi сан бар болады және де дәл осындай түрде болады:
a*a-1 ≡ 1 (mod n)
Шындығында да, a*i (mod n) 0, 1, …, n-1 алмастыруы болып табылады, сондықтан i бар болады және төмендегідей түрде болады:
a*i ≡ 1 (mod n)
Мысалы, n = 11-жай сан болсын. 11 модуль бойынша шегерудiң толық жиыны {0, 1, 2, …, 10}.
Келтiрiлген шегеру жиынын тұжырымдаған кезде олардың iшiнен бiр ғана элемент – 0 өшiрiледi. Келтiрiлген шегеру жиыны 11 модулi бойынша 11-1 = 10 элементi бар болады.
Жалпы келтiрiлген шегеру жиынында n модуль бойынша жай санының n-1 элементi бар болады.
Эйлер функциясы φ(n) шегеру жиынтығында келтірілген элементтер санын мінездейді. Төмендегі кестеден көруге болады.
Кесте 1 Эйлер функциясы
| Модуль n | Функция φ(n) |
| N – жай сан
n2 |
n-1
n(n-1) nr-1(n-1) |
| P*q (p, q – жай сандар)
(p– жай сан) |
(p-1)(q-1)
|
Басқаша айтқанда, Ферманың кiшкене теоремасы: егер n–жай және ЕҮОБ(a, n) = 1, онда an-1 ≡ 1 (mod n) болады.
Эйлердiң қортуына сәйкес Ферманың кiшене теоремасынан: eгер ЕҮОБ(a, n) = 1, онда aφ(n) ≡ 1 (mod n)-ге тең.
Керi шаманы табудың негiзгi 3 әдiсі бар. Олар: тура іріктеу әдісі, евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды есептеу әдісі, Эйлер функциясы көмегімен кері шамаларды есептеу әдісі. Соларға тоқталайық.