ძირითადი მასალა

კომპიუტერული მეცნიერება

კურსი: კომპიუტერული მეცნიერება > თემა 2

გაკვეთილი 5: მოდულარული არითმეტიკა

სადარობა

Google–ის საკლასო ოთახი

სადარობა

შეიძლება, ნახოთ შემდეგი სახის გამოსახულება:

$A \equiv B (mod C)$ ‍

ეს ამბობს, რომ

A

სადარია

B

-ს mod

C

ჩვენ განვიხილავთ სადარობის არსს რეგულარული ნაშთის ოპერატორზე წარმოსახვითი ექსპერიმენტის ჩატარებით.

წარმოვიდგინოთ, რომ ვითვლიდით ყველა მთელი რიცხვის ნაშთს 5-ზე:

ვთქვათ, 5 ნაჭერს დავარქვით 0, 1, 2, 3, 4. მაშინ თითოეულ მთელ რიცხვს ვსვამთ ნაჭერში, რომელიც ემთხვევა ამ მთელი რიცხვის ნაშთს 5-ზე.
იფიქრეთ ამ ნაჭრებზე, როგორც ყუთებზე, რომლებშიც მოთავსებულია რიცხვების სიმრავლე. მაგალითად, 26 მოთავსდებოდა ყუთში 1, რადგან

26 mod 5 = 1

.
ზემოთ მოცემულია, ფიგურა, რომელიც აჩვენებს რამდენიმე მთელ რიცხვს, რომელთაც ვიპოვიდით თითოეულ ნაჭერში.

გამოსადეგი იქნებოდა, რომ გვქონდეს იმავე ნაჭერში თავსებადი რიცხვების გამოსახვის საშუალება (აღვნიშნოთ, რომ 26 არის იგივე ნაჭერში, რომელშიც 1, 6, 11, 16, 21 ზემოთ მოცემულ მაგალითში).

ერთ ნაჭერში მყოფი ორი რიცხვის გამოხატვის გავრცელებული გზა არის იმის თქმა, რომ ისინი ერთსა და იმავე ეკვივალენტობის კლასში არიან.
ამის მათემატიკური გამოსახვის საშუალება mod C-სთვის არის:

A \equiv B (mod C)

ზემოთ მოცემული გამოსახულება შემდეგნაირად გამოითქმის:

A

სადარია

B

-სი mod

C

გამოსახულების გაანალიზება უფრო დეტალურად:

$\equiv$ ‍ არის კონგრუენტულობის სიმბოლო, რაც ნიშნავს, რომ მნიშვნელობები $A$ ‍ და $B$ ‍ ერთსა და იმავე ეკვივალენტობის კლასში არიან.
$(mod C)$ ‍ გვეუბნება, რა ოპერაცია გამოვიყენეთ $A$ ‍-სა და $B$ ‍-ზე.
როდესაც ორივე მათგანი გვაქვს, ვამბობთ „ $\equiv$ ‍“ სადარობა mod $C$ ‍.

მაგალითად,

26 \equiv 11 (mod 5)

26 mod 5 = 1

ასე რომ, ეს არის ეკვივალენტობის კლასი 1-ისთვის,

11 mod 5 = 1

ასე რომ, ესეც არის ეკვივალენტობის კლასი 1-ისთვის.

აღვნიშნოთ, რომ ეს არ არის იგივე, რაც

A mod C

26 \neq 11 mod 5

დეტალები სადარობაზე

მეტი დეტალის გაგება შეგვიძლია სადარობის შესახებ დადებითი მთელი რიცხვის გამოყენებით ფიქრის ერთი და იგივე ექსპერიმენტის ჩატარებით $C$ ‍.
ჯერ $C$ ‍ ნაჭერს დავარქმევდით $0, 1, 2, \dots, C - 2, C - 1$ ‍-ს.
შემდეგ თითოეულ მთელ რიცხვს ჩავსვამდით ყუთში, რომელიც ემთხვევა ამ მთელ რიცხვს $mod C$ ‍.
ქვემოთ მოცემულ ფიგურაზე ნაჩვენებია რამდენიმე მნიშვნელობა, რომელთაც ვიპოვიდით თითოეულ ნაჭერში.

თუ შევხედავდით 0-ით გადანომრილ ყუთს, ვნახავდით:

$\dots, - 3 C, - 2 C, - C, 0, C, 2 C, 3 C, \dots$ ‍

თუ შევხედავდით 1-ით გადანომრილ ყუთს, ვნახავდით:

$\dots, 1 - 3 C, 1 - 2 C, 1 - C, 1, 1 + C, 1 + 2 C, 1 + 3 C, \dots$ ‍

თუ შევხედავდით 2-ით გადანომრილ ყუთს, ვნახავდით:

$\dots, 2 - 3 C, 2 - 2 C, 2 - C, 2, 2 + C, 2 + 2 C, 2 + 3 C, \dots$ ‍

თუ შევხედავდით $C - 1$ ‍-ით გადანომრილ ყუთს, ვნახავდით:

$\dots, - 2 C - 1, - C - 1, - 1, C - 1, 2 C - 1, 3 C - 1, 4 C - 1 \dots$ ‍

ამ ექსპერიმენტიდან შეგვიძლია, გავაკეთოთ საკვანძო დაკვირვება:
მნიშვნელობები თითოეულ ნაჭერში ტოლია ამ ნაჭრის სახელის პლუს ან მინუს $C$ ‍-ს რაიმე ჯერადი.
ეს ნიშნავს, რომ ორ ნებისმიერ მნიშვნელობას შორის სხვაობა ნაჭერში არის $C$ ‍-ს რაიმე ჯერადი.
ეს დაკვირვება დაგვეხმარება, გავიაზროთ ეკვივალენტური დებულებები და ეკვივალენტობის კლასები შემდეგში.

გსურთ, შეუერთდეთ დისკუსიას?

შესვლა

დავალაგოთ:

პოსტები ჯერ არ არის.

გესმით ინგლისური? დააწკაპუნეთ აქ და გაეცანით განხილვას ხანის აკადემიის ინგლისურენოვან გვერდზე.