ლექცია 19, რიცხვთა თეორია

1. რიცხვი იდეალურია, თუ იგი ტოლია თავისი გამყოფების (თავისი თავის გარდა) ჯამის. მაგალითად, 6 იდეალურია, რადგან 6 = 1+2+3. ასევე, 28 იდეალურია, რადგან 28 = 1+2+4+7+14. ახსენით, რატომ იქნება 2^(k−1) * (2^k −1) იდეალური, როცა 2^k −1 მარტივია.

თუ 2^k-1 მარტივია, მაშინ 2^(k−1) * (2^k −1)-ის ერთადერთი გამყოფებია:

• 1, 2, 4, ... , 2^(k-1), რაც ჯამში ტოლია 2^k-1 -ის, და~
• 1*(2^k −1), 2*(2^k −1), 4*(2^k −1), ..... , 2^(k-2) * (2^k - 1), რაც ჯამში არის (2^(k-1) - 1) * (2^k - 1)

ამ ორის შეკრებით მიიღება 2^(k−1) * (2^k −1), ანუ რიცხვი იდეალურია.

2.
ა) დაამტკიცეთ, რომ თუ გვაქვს ორი ჭურჭელი, 21–ლიტრიანი და 26–ლიტრიანი, და ვდგავართ მდინარის პირას, მაშინ მათი საშუალებით შეიძლება მივიღოთ ზუსტად 3 ლიტრი წყალი (და საერთოდ, ნებისმიერი მთელი რაოდენობა ლიტრები 0–დან 26–მდე).

ბ) როგორი რაოდენობები შეიძლება მივიღოთ, თუ გვაქვს 21–ლიტრიანი და 27–ლიტრიანი ჭურჭლები?

3. Problem 14.2.
 (a) Use the Pulverizer to find integers x,y such that
x * 50 + y * 21 = gcd(50, 21).

(b) Now find integers x',y' with y' > 0 such that
x' * 50 + y' * 21 = gcd(50, 21)

მითითება: გამოიყენეთ ევკლიდეს ალგორითმი (მაგალითისთვის ნახეთ პუნქტი 14.2.4, გვ. 282).

4. (a) Let m = 2^9 * 5^24 * 11^7 * 17^12 and n = 2^3 * 7^22 * 11^211 * 13^1 * 17^9 * 19^2.
What is the gcd(m, n)?
What is the least common multiple, lcm(m, n), of m and n?
Verify that

gcd(m, n) · lcm(m, n) = mn.        ---- equation 14.5

(b) Describe in general how to find the gcd(m, n) and lcm(m, n) from the prime
factorizations of m and n. Conclude that equation (14.5) holds for all positive integers
m, n.

5. აღწერეთ 287-ე გვერდზე მოცემული თიურინგის კოდის მოქმედება და მიუთითეთ რა შემთხვევაში შეიძლება მისი გატეხვა.