Solving Relatively Prime Homework Without Fractions

[scorpius1782]

Homework Statement

For integers a,b, and c, if a and c are relatively prime and c|ab, then c|b.
Knowing that: For any integers p and q, there are integers s and t such that gcd(p,q) = sp + tq.

The hint I'm given is that I should form an equation from the fact that they are "relatively prime."
The last caveat is that I cannot use fractions at all in my proof.

Homework Equations

The Attempt at a Solution

So my hang up is definitely the equation for relatively prime. As I understand it for relatively prime: gcd(a,c)=1. Then, I suppose I could just use the given equation to say that 1= sa + tc. (I believe this Bézout's identity).

Then I have the following claim: If 1= sa + tc and ab=cn then b=cp. Where n and p are just integers. Then I can say that sa=1-tc. Then multiplying the second condition by 's' I'd have sab=scn. Combining them b(1-tc)=scn.

But I can't do fractions so I'm not sure what to make of this, or if I've even started the problem correctly. I find it unlikely that my relatively prime equation is correct, or is what they intended me to do.

Thanks for the suggestions.

 

[Simon Bridge]

so you mean you have to prove
if gcd(c,a)=1
and gcd(c,ab)=1
then gcd(c,b)=1

I don't see how you got ab=cn.
Go thorugh it more cereafully: express each of the lines using Bezouts ID... you end up with three similar looking expressions. don't forget the entire identity.

 

[scorpius1782]

Maybe the way we write things is different.
gcd(c,a)=1 is relatively prime
c|ab means that ab is divisible by c. Or, written another way c(n)=ab where n is just some integer.
And, of course c|b just means that b is divisible by c or c(p)=b.

I'm not sure if you understood me or if I don't understand you.

 

[scorpius1782]

Well, I think I've got it. I had to do one operation to rearrange an equation that may/may not be seen as division but I think I'm safe. Thanks for the help anyway.

 

[Simon Bridge]

Oh I see - right... c|ab would be nc=ab: n is an integer.
In this example, everything is an integer - so combinations of them that do not involve division are also integers.

...so you need only show that nc=ab and sc+ta=1 both being true means that b = [some integer]c.
Whatever ends up in the brackets will be an integer so long as it does not include a division: i.e. that's not a restriction, it's a hint!

Looking back at post #1: you got stuck at:
b(1-tc)=scn.

... all you need from there is to do some algebra so that you get

b = [some stuff]c

... then check that the [some stuff] is an integer.

 

[kduna]

b(1-tc)=scn

You are almost there, play around with this equation.

 

[scorpius1782]

Yeah, I was able to multiply that equation with a another variable and combine everything so that the b was able to come out and everything else became an integer on the other side. The trick to this was just figuring out what to multiply what by.

 

[kduna]

Yeah, I was able to multiply that equation with a another variable and combine everything so that the b was able to come out and everything else became an integer on the other side. The trick to this was just figuring out what to multiply what by.

You seem to be working too hard.

b(1-tc) = b - btc.

 

[scorpius1782]

I suppose I could say ##b-btc=scn \implies b=scn+btc \implies b=c(sn+bt)## I saw this and was a little hesitant because I wasn't sure about having the 'b' in there with the other integers. I mean the quantity could be anything but is still dependent on 'b'. I'm not sure it really matters or not, though.

 

[Simon Bridge]

When you have done this sort of algebra in the past, you are usually asked to find an actual value for b or c or whatever - so it is not helpful to mix up variables like that.

In this case it does not matter because you only need the relationship b=[some integer]c - you are not trying to find out what that integer is or what any of the values are. All you care about is that it is an integer.

 

[kduna]

I suppose I could say ##b-btc=scn \implies b=scn+btc \implies b=c(sn+bt)## I saw this and was a little hesitant because I wasn't sure about having the 'b' in there with the other integers. I mean the quantity could be anything but is still dependent on 'b'. I'm not sure it really matters or not, though.

It is perfectly ok for b to be in there with the other integers .

For example 6 = 2(3*3 - 6*1). Here b = 6 and c = 2.

 

[scorpius1782]

I've updated my proof with this. It is certainly far easier to do than the shenanigans I used before. While what I had should have been correct it took a very long time to get there.

I originally thought this was going to end up being the way things worked out but as soon as I got that b on the right side I just thought it looked to weird. I struggled with this for a couple days off and on trying to find a way to make it work without having b over there; and all this time I really had the problem all but finished if I had just done what I originally wanted to do.

Thanks a lot for the help!