Қазақша рефераттар

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

Сандар теориясы

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

Нақты сандарда мультипликативті кері шаманы табу әдетте қиын емес. Ал модулярлық арифметикада кері элементтің бар-жоғы және оны табу тәсілі маңызды есептердің бірі болып саналады.

Нақты сандардағы кері шама және модулярлық ерекшелік

Нақты сандар арифметикасында нөлден өзге a санының мультипликативті кері шамасы оңай табылады: a·a-1 = 1. Мысалы, 4 санының кері шамасы 1/4, өйткені 4·(1/4)=1.

Ал модулярлық арифметикада кері элементті табу әрдайым мүмкін бола бермейді және оның бар болуы a мен n сандарының өзара жай болуына тәуелді.

Кері элементті теңдеу арқылы түсіндіру

Мысал: 4·x ≡ 1 (mod 7)

4·x ≡ 1 (mod 7) салыстыруын шешу 4·x = 7·k + 1 теңдеуіндегі x және k бүтін сандарын табумен теңмәнді.

Жалпы тұжырым: a·x ≡ 1 (mod n) теңдеуінің шешімі болса, онда a-1 ≡ x (mod n) деп жазамыз.

Шешім әрдайым бола ма?

Бұл есептің шешімі кейде бар, кейде жоқ.

  • Мысал (бар): 5 санының 14 модулі бойынша кері элементі 3, өйткені 5·3 = 15 ≡ 1 (mod 14).
  • Мысал (жоқ): 2 санының 14 модулі бойынша кері элементі жоқ, өйткені ЕҮОБ(2, 14) ≠ 1.

Кері элементтің бар болу шарты және бірмәнділігі

Егер a және n — өзара жай сандар болса (ЕҮОБ(a, n)=1), онда a-1 ≡ x (mod n) салыстыруының шешімі бар және ол n модулі бойынша бірмәнді (яғни бір ғана қалдық класына сәйкес келеді).

Ал ЕҮОБ(a, n) ≠ 1 болса, онда мультипликативті кері элемент болмайды.

Алмастыру (перестановка) идеясы

a ∈ {0, 1, 2, …, n-1} болсын. Егер ЕҮОБ(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 3 4 5 6
3·i (mod 7): 0 3 6 2 5 1 4

Демек, бұл {0,1,2,3,4,5,6} жиынының алмастыруы.

Қарсы мысал: a = 2, n = 6

ЕҮОБ(2,6)≠1, сондықтан қалдықтар қайталанады:

i: 0 1 2 3 4 5
2·i (mod 6): 0 2 4 0 2 4

Мұнда 1, 3, 5 қалдықтары мүлде шықпайды, сондықтан кері элемент те болмайды.

Осыдан шығатын қорытынды

Егер ЕҮОБ(a, n)=1 болса, онда кері элемент міндетті түрде бар және a·a-1 ≡ 1 (mod n) орындалады. Себебі алмастыру қасиеті бойынша міндетті түрде бір i табылады да, a·i ≡ 1 (mod n) болады; сол i — ізделінетін кері элемент.

Келтірілген шегерулер және Эйлер функциясы

n = 11 жай сан болсын. Онда 11 модулі бойынша толық қалдықтар жүйесі {0,1,2,…,10}. Ал келтірілген шегерулер жүйесі осы жиыннан 0 элементін алып тастағанда шығады, яғни n-1 = 10 элементтен тұрады.

Жалпы жағдайда Эйлер функциясы φ(n) — n модулі бойынша n-мен өзара жай болатын қалдықтар саны.

Эйлер функциясының кейбір мәндері

Модуль n Функция φ(n)
n — жай сан n − 1
n = p2 (p — жай сан) p(p − 1)
n = pr (p — жай сан, r ≥ 1) pr−1(p − 1)
n = p·q (p, q — жай сандар) (p − 1)(q − 1)

Ферма және Эйлер теоремалары

Ферманың кіші теоремасы

Егер n — жай сан және ЕҮОБ(a, n)=1 болса, онда an−1 ≡ 1 (mod n).

Эйлер теоремасы

Ферманың теоремасын жалпылай отырып, Эйлер қорытындысы бойынша: егер ЕҮОБ(a, n)=1 болса, онда aφ(n) ≡ 1 (mod n).

Кері шаманы табудың негізгі әдістері

Модулярлық арифметикада кері элементті табудың негізгі үш әдісі жиі қолданылады:

  1. 1) Тура іріктеу әдісі

    a·x ≡ 1 (mod n) теңдігін қанағаттандыратын x-ті барлық мүмкін қалдықтар ішінен тексеріп табу.

  2. 2) Евклидтің кеңейтілген алгоритмі

    ax + ny = 1 түріндегі теңдеуді шешу арқылы кері элементті тиімді есептеу.

  3. 3) Эйлер функциясы арқылы

    aφ(n) ≡ 1 (mod n) қатынасын қолданып, aφ(n)−1 арқылы кері элементке келу.

Келесі бөлімдерде осы әдістердің әрқайсысы нақты есептер арқылы қарастырылуы мүмкін.

Ескерту: Барлық теңдеулерде x, k, y — бүтін сандар.