Модулярлық арифметикада кері шамаларды есептеу туралы қазақша реферат

Модулярлық арифметикада кері шамаларды есептеу туралы қазақша реферат

Нақты сандарды арифметикада а-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сі бар. Олар: тура іріктеу әдісі, евклидтің кеңейтілген алгоритмі көмегімен кері шамаларды есептеу әдісі, Эйлер функциясы көмегімен кері шамаларды есептеу әдісі. Соларға тоқталайық.