Дефиниција: Нека се дадени два релативно прости (цели броеви) \color{green}{m} и \color{red}{n} каде што m>n .

Ојлеров метод е алгоритам со кој може да се нajдaт цели броеви \color{teal}{p} и \color{purple}{q} такви што \color{green}{m}\cdot \color{teal}{p}+\color{red}{n}\cdot \color{purple}{q} = \color{magenta}{1}

Пример 1:   m = \color{green}{7} и n= \color{red}{-2}

Чекор q

Количник

r

Остаток

Замена Комбинација
1   \color{green}{7}   \color{green}{7}=\color{green}{7} \cdot 1 + \color{red}{-2} \cdot 0
2   \color{red}{-2}   \color{red}{-2}= \color{green}{7} \cdot 0 + (\color{red}{-2}) \cdot 1
3 \color{purple}{-3} \color{magenta}{1}=\color{green}{7}-(\color{red}{-2}) \cdot \color{purple}{-3} \color{magenta}{1}=(\color{green}{7} \cdot 1 + (\color{red}{-2}) \cdot 0 \cdot 1) -(\color{green}{7} \cdot 0 + (\color{red}{-2}) \cdot 1) \cdot \color{purple}{-3} \color{magenta}{1}=\color{green}{7} \cdot 1 + (\color{red}{-2}) \cdot (3)
Имаме: \color{magenta}{1}=\color{green}{7} \cdot (1) + (\color{red}{-2}) \cdot (3) .
Одговор на задачата: \color{teal}{p}=\color{teal}{1} и \color{purple}{q}=\color{purple}{3} .

Пример 2:   m = \color{green}{17} и n= \color{red}{3}

Чекор q

Количник

r

Остаток

Замена Комбинација
1   \color{green}{17}   \color{green}{17}=\color{green}{17} \cdot 1 + \color{red}{3} \cdot 0
2   \color{red}{3}   \color{red}{3}= \color{green}{17} \cdot 0 + \color{red}{3} \cdot 1
3 \color{purple}{5} \color{teal}{2}=\color{green}{17}-\color{red}{3} \cdot \color{purple}{5} \color{teal}{2}=(\color{green}{17} \cdot 1 + \color{red}{3} \cdot 0 \cdot 1) -(\color{green}{17} \cdot 0 + \color{red}{3} \cdot 1) \cdot \color{purple}{5} \color{teal}{2}=\color{green}{17} \cdot 1 + \color{red}{3} \cdot (-5)
4 \color{blue}{1} \color{magenta}{1}=\color{red}{3}-\color{teal}{2} \cdot \color{blue}{1} \color{magenta}{1}=\color{green}{17} \cdot 0 + \color{red}{3} \cdot 1 -(\color{green}{17} \cdot 1 + \color{red}{3} \cdot (-5)) \cdot \color{blue}{1} \color{magenta}{1}=\color{green}{17} \cdot (-1) + \color{red}{3} \cdot (6)
Имаме: \color{magenta}{1}=\color{green}{17} \cdot (-1) + \color{red}{3} \cdot (6) .
Одговор на задачата: \color{teal}{p}=\color{teal}{-1} и \color{purple}{q}=\color{purple}{6} .

Пример 3:   m = \color{green}{59} и n= \color{red}{27}

Чекор q

Количник

r

Остаток

Замена Комбинација
1   \color{green}{59}   \color{green}{59}=\color{green}{59} \cdot 1 + \color{red}{27} \cdot 0
2   \color{red}{27}   \color{red}{27}= \color{green}{59} \cdot 0 + \color{red}{27} \cdot 1
3 \color{purple}{2} \color{teal}{5}=\color{green}{59}-\color{red}{27} \cdot \color{purple}{2} \color{teal}{5}=(\color{green}{59} \cdot 1 + \color{red}{27} \cdot 0 \cdot 1) -(\color{green}{59} \cdot 0 + \color{red}{27} \cdot 1) \cdot \color{purple}{2} \color{teal}{5}=\color{green}{59} \cdot 1 + \color{red}{27} \cdot (-2)
4 \color{blue}{5} \color{darkyellow}{2}=\color{red}{27}-\color{teal}{5} \cdot \color{blue}{5} \color{darkyellow}{2}=\color{green}{59} \cdot 0 + \color{red}{27} \cdot 1 -(\color{green}{59} \cdot 1 + \color{red}{27} \cdot (-2)) \cdot \color{blue}{5} \color{darkyellow}{2}=\color{green}{59} \cdot (-5) + \color{red}{27} \cdot (11)
5 \color{darkgreen}{2} \color{magenta}{1}=\color{teal}{5}-\color{darkyellow}{2} \cdot \color{darkgreen}{2} \color{magenta}{1}=(\color{green}{59} \cdot 1 + \color{red}{27} \cdot (-2))-(\color{green}{59} \cdot (-5) + \color{red}{27} \cdot (11)) \cdot \color{darkgreen}{2} \color{magenta}{1}=\color{green}{59} \cdot (11) + \color{red}{27} \cdot (-24)
Имаме: \color{magenta}{1}=\color{green}{59} \cdot (11) + \color{red}{27} \cdot (-24) .
Одговор на задачата: \color{teal}{p}=\color{teal}{11} и \color{purple}{q}=\color{purple}{-24} .

Поврзани теми:


 Нагоре македонски речник математика makedonski recnik matematika