Discrete Mathematics Division Algorithm proof I'm not quite sure how to do this problem if anyone c

spazzter08dyk2n

spazzter08dyk2n

Answered question

2022-05-11

Discrete Mathematics Division Algorithm proof
I'm not quite sure how to do this problem if anyone can do a step by step to help me understand it I would appreciate it a lot.
Let a and b be positive integers with b > a, and suppose that the division algorithm yields b = a q + r, with 0 r < a. (note: its a zero)
Prove that l c m ( a , b ) l c m ( a , r ) = a 2 q gcd ( a , b ) .

Answer & Explanation

HowOPpodopgtk3

HowOPpodopgtk3

Beginner2022-05-12Added 20 answers

Step 1
Using the Euclidean algorithm for gcd:
(1) gcd ( a , b ) = gcd symmetric gcd ( b , a ) = def.  b gcd ( a q + r , a ) = Eucl. gcd ( a , r ) .
Step 2
Also, it is a fact that for any integers x , y 0:
(2) lcm ( x , y ) = x y gcd ( x , y ) .
Combining these facts, you get:
lcm ( a , b ) lcm ( a , r )   = ( 2 )   a b gcd ( a , b ) a r gcd ( a , r )   = ( 1 )   a ( b r ) gcd ( a , b )   = def.  b   a ( a q ) gcd ( a , b ) .

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?