# Prove largest positive integer dividing a and b is 1

• Feb 22nd 2009, 02: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, 02: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 $\displaystyle d|a \implies a=q_1d$ for some $\displaystyle q_1 \in \mathbb{Z}$

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

Now lets plug these into the first equation

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

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

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

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

So this statement tells us that $\displaystyle d|1$

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

TES
• Feb 22nd 2009, 02: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