Mathcasts Examples Practice More E
Definition : Given 2 relatively prime integers \color{green}{m} and \color{red}{n} where m>n .
Euler's Algorithm is a method for finding integers
\color{teal}{p} and
\color{purple}{q} such that
\color{green}{m}\cdot \color{teal}{p}+\color{red}{n}\cdot \color{purple}{q} = \color{magenta}{1}
m = \color{green}{7} and n= \color{red}{-2}
Step
q
Quotient
r
Remainder
Substitution
Result
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)
We have:
\color{magenta}{1}=\color{green}{7} \cdot (1) + (\color{red}{-2}) \cdot (3) .
Answer: \color{teal}{p}=\color{teal}{1} и
\color{purple}{q}=\color{purple}{3} .
m = \color{green}{17} and n= \color{red}{3}
Step
q
Quotient
r
Remainder
Substitution
Result
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)
We have:
\color{magenta}{1}=\color{green}{17} \cdot (-1) + \color{red}{3} \cdot (6) .
Answer: \color{teal}{p}=\color{teal}{-1} и
\color{purple}{q}=\color{purple}{6} .
m = \color{green}{59} и n= \color{red}{27}
Step
q
Quotient
r
Remainder
Substitution
Result
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)
We have:
\color{magenta}{1}=\color{green}{59} \cdot (11) + \color{red}{27} \cdot (-24) .
Answer: \color{teal}{p}=\color{teal}{11} и
\color{purple}{q}=\color{purple}{-24} .
Related Topics:
Up one level
