Урок Тема «Найбільший спільний дільник» 8 клас Автор: учитель математики Дронова Тетяна Іванівна (Богодухівська гімназія 1)

Перевірка домашнього завдання Конгруенції та їх властивості

Конгруентності та їх властивості

)84 = 12 (mod 9); 2)-26 = 4 (mod 6); 3)8 = -3 (mod 11); За необхідною і достатньою умовою

Самостійна робота Замість знака * запишіть таке найменще невідємне число, щоб отримана конгруенція була правильною Варіант-1 Варіант-2

Відповіді до самостійної роботи Варіант-1 Варіант-2

Ділимо число a на b, якщо Алгоритм Евкліда для знаходження НСД чисел a і b полягає у виконанні наступних дій : то за лемою 1 (a,b)=b. Якщо то отримуємо остачу r 1 : a=bq 0 +r 1 ; Ділимо b на r 1, якщо то (b,r 1 )= r 1, і згідно з лемою 2 (a, b)=(b, r 1 )= r 1, якщо то маємо остачу r 2 : b= r 1 q 1 +r 2 ; Ділимо r 1 на r 2 і знову можливі два випадки: якщо то (r 1, r 2 )=(b, r 1 )=(a,b), або r 1 ділиться на r 2 з остачею r 3 і т.д. Оскільки остачі, які отримуються в процесі ділення, то вони є спадними натуральними числами, і на якомусь кроці ми отримуємо остачу, рівну 0, а остання, не рівна 0 остача, і буде найбільшим спільним дільником чисел a і b.