# Prove largest positive integer dividing a and b is 1

• Feb 22nd 2009, 03:29 PM
teacast
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!
• Feb 22nd 2009, 03:43 PM
TheEmptySet
Quote:

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 $d|a \implies a=q_1d$ for some $q_1 \in \mathbb{Z}$

if $d|b \implies b=q_2d$ for some $q_2 \in \mathbb{Z}$

Now lets plug these into the first equation

$5(q_1d)-3(q_2d)=1$ now we can factor out the common d in each term on the left to get

$d(5q_1-3q_2)=1$

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

$dq_3=1$ for some $q_3 \in \mathbb{Z}$

So this statement tells us that $d|1$

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

TES
• Feb 22nd 2009, 03:49 PM
teacast
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!