# Solving Relatively Prime Homework Without Fractions

• scorpius1782
In summary, the student is trying to solve an equation for a, c, and b that are relatively prime. They ran into a problem with the equation and are not sure if it is correct or not. They are almost done and can solve for b.
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.

## 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.

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.

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.

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.

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.

1 person
scorpius1782 said:
b(1-tc)=scn

You are almost there, play around with this equation.

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.

scorpius1782 said:
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.

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.

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.

scorpius1782 said:
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.

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!

## 1. What does it mean for numbers to be relatively prime?

Two numbers are relatively prime if they share no common factors besides 1. This means that the greatest common divisor of the two numbers is 1.

## 2. How do I know if two numbers are relatively prime?

To determine if two numbers are relatively prime, you can find the greatest common divisor (GCD) of the two numbers. If the GCD is equal to 1, the numbers are relatively prime. You can also check if the prime factorization of the two numbers have any common factors. If they do not have any common factors, they are relatively prime.

## 3. Why is it important to solve relatively prime homework without fractions?

Solving relatively prime homework without fractions is important because it simplifies the problem and makes it easier to find the solution. Fractions can often make problems more complicated and time-consuming to solve, so eliminating them can save time and make the problem more manageable.

## 4. What strategies can I use to solve relatively prime homework without fractions?

One strategy is to factor the numbers and then eliminate any common factors to make them relatively prime. Another strategy is to use the Euclidean algorithm to find the GCD of the two numbers, which can then be used to determine if the numbers are relatively prime. Additionally, you can use a calculator or online tool to quickly determine if two numbers are relatively prime.

## 5. Can I use the same methods to solve relatively prime homework with fractions?

Yes, you can use the same methods to solve relatively prime homework with fractions. However, you will need to find a common denominator and convert the fractions into equivalent fractions with the same denominator before applying the methods. This will help eliminate fractions and make the problem more manageable.

• Calculus and Beyond Homework Help
Replies
5
Views
1K
• Calculus and Beyond Homework Help
Replies
5
Views
2K
• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
16
Views
2K
• Calculus and Beyond Homework Help
Replies
3
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
2K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
5
Views
2K
• Calculus and Beyond Homework Help
Replies
6
Views
2K