Thread: Prove largest positive integer dividing a and b is 1

Hey everyone, I can't figure this out (I don't understand how to get there), it seems simple but it is just frustrating the life out of me!

Let a and b be integers such that 5a - 3b = 1. Prove that the largest positive integer dividing both a and b is 1.

My professor told me to start by saying "Let d be a positive integer that divides both a and b, then d divides ?"

It doesn't really help me as I have no idea how to approach this.

Any help/explanation would be fantastic!

Originally Posted by teacast

Hey everyone, I can't figure this out (I don't understand how to get there), it seems simple but it is just frustrating the life out of me!

Let a and b be integers such that 5a - 3b = 1. Prove that the largest positive integer dividing both a and b is 1.

My professor told me to start by saying "Let d be a positive integer that divides both a and b, then d divides ?"

It doesn't really help me as I have no idea how to approach this.

Any help/explanation would be fantastic!

starting with the hint from your prof we get

if for some


if for some

Now lets plug these into the first equation

now we can factor out the common d in each term on the left to get



Since the integers are closed under addition and subtraction we get that

for some

So this statement tells us that

The only divisors of 1 are so a and b must be relativley prime.

TES

ohhh I see how you did that, very clever (I wish I could prove like that!).

One more question, I also have to prove that since r+s, r-s and rs are rational, prove that r/s is rational.

I said that:

r = a/b s = c/d

a/b + c/d = ad+bc/bd

if b and d do not equal 0, then it is rational



I did two similar proofs regarding a denominator in r-s and rs,
not sure if it is right though.... Thanks for the help!