ლექცია 21 Number theory, Arithmetic with an arbitrary modulus

1)დაასაბუთეთ, რომ φ(p^k)=p^k-p^(k-1), სადაც p ნებისმიერი მარტივი რიცხვია, ხოლო φ წარმოადგენს ეილერის ფუნქციას. 

ჯერ განვმარტოთ თუ რა არის φ(n), ანუ ეილერის ფუნქცია, ეილერის ფუნქცია n - ისთვის არის 1 დან n - მდე ყველა n - თან თანამარტივი რიცხვის რაოდენობა.

ჯერ 1 დან p^k-ს ჩათვლით სულ p^k რიცხვების სიმრავლე, რომელშიც სულ p^k ელემენტი იქნება. ამ სიმრავლეს ჩვენ უნდა გამოვაკლოთ ყველა ისეთი რიცხვი, რომელიც p^k - სთან თანამარტივი არაა, ეს რიცხვები იქნება:

1p;2p;3p;4p...........p^(k-1)p - ამ სიმრავლეში ელემენტების რაოდენობა იქნება p^(k-1), სულ კი p^k რიცხვი გვაქვს, შესაბამისად სხვაობაში გვექნება φ(p^k)=p^k-p^(k-1);

2,3) გამოთვალეთ φ(18) და იპოვეთ 5-ს შებრუნებული 18-ს მოდულით;

φ(18)=φ(2)*φ(3^2)=φ(2)*(3^2-3^1) (წინა ამოცანიდან გამომდინარე, რადგანაც 3 მარტივი რიცხვია).

φ(18)=1*6=6;

რიცხვის შებრუნებული ეწოდება ისეთ რიცხვს, რომელის საწყის რიცხვზე გამრავლებისასაც ვიღებთ 1-ს მოდულით რაღაც კონკრეტული n

ჩვენ ვიცით, რომ a^φ(n)=1 mod(n) , შესაბამისად a*a^(φ(n)-1)=1 mod(n) ვიცით, რომ a^φ(18)=a^6=a*a^5=1 mod(n);

Problem 14.11

ბ) გამოთვალეთ φ(175)
φ(175)=φ(25)*φ(7)=(5^2-5^1)*6=20*6=120

ა) დაამტკიცეთ, რომ  22^12001 აქვს შებრუნებული მოდულით 175
22^φ(175)=1 mod(175) -> (22^φ(175))^t=1 mod(175) სადაც t რაღაც მთელი რიცხვია;
შესაბამისად
22^φ(175)=22^120=(22^120)^100=1 mod(175);
22^12001=22^12000*22=22 mod(175)
22^12000*22*22^(φ(175)-1)=1 mod(175);
(ვინაიდან 22^12000=1 და 22*22^(φ(175)-1)=22^φ(175)=1)
ესეიგი შებრუნებული რიცხვი არის 22^(φ(175)-1) = 22^119

გ) რა არის 22^12001-ს ნაშთი 175 ზე გაყოფისას
ზედა ამოცანაში უკვე დავამტკიცეთ, რომ არის 22;

Problem 14.12
ა) დაიანგარიშეთ ისეთი s და t რომ:
40s +7t = gcd(40, 7). 

ვიყენებთ pulverizer-ს

gcd (40 , 7)=(7,33)=(7,26)=(7,19)=(7,12)=(7,5)=(5,2)=(2,3)=(2,1)=(1,1)=(1,0)

სულ 10 ნაბიჯი შესაბამისად s=10 დავითვლით t -საც t=-57
მართლაც 10*40-57*7=1

ბ) დაიანგარიშეთ 40-ს შებრუნებული 7-ს ფუძით 1 დან 39 მდე;
ერთი ვარიანტია s ის მნიშვნელობა დავტოვოთ, ანუ შებრუნებული = 10,

მეორე ვარიანტია
s40+t7=1 განტოლების მარცხენა მხარეს დავუმატოთ 40*7 და გამოვაკლოთ 40*7 

s40-40*7+t7+40*7=40(s-7)+7*(t+40)=1 განტოლება სწორია, რადგანაც (+)40*7+(-)40*7=0 და 0 ს დამატება არაფერს არ ცვლის.

შესაბამისად
10-7=3 და მეორე შებრუნებული იქნება 3;

ეს რატის დაწერილია და თუ ვერ გაიგეთ, ალბათ იმიტომ, რომ ევკლიდეს გავრცობილი ალგორითმი არ იცოდით (მე არ ვიცოდი და მაგიტომ ვერ გავიგე :) ). ასე რომ, შევეცდები აგიხსნათ.

ევკლიდეს ალგორითმით, თუ გვინდა ვიპოვოთ a-ს შებრუნებულის n-ის მოდულით, ვაკეთებთ ასეთ რაღაცას (იგულისხმება, რომ თითოეული ტოლობა n-ის მოდულითაა):

ax = 1;  სადაც x არის a-ს შებრუნებული. ვინაიდან n ყოფს ax-1-ს:
ax-1 = qn;  სადაც q რაიმე მთელი რიცხვია. გადავალაგოთ:
ax - qn = 1;

განხილულ მაგალითში, a = 40 და შესაბამისად x=10 - ეს პირველ შემთხვევაში.
მეორე შემთხვევაში x=s-7, ანუ 10-7-ს.