Abstract/Modern Algebra - Relatively Prime

  • Thread starter b0it0i
  • Start date
  • #1
36
0

Homework Statement


Note: gcd(a,b) = the greatest common divisor of integers a and b (not both 0)

suppose that (a,b)=1 and (a,c)=1
that is, a and b are relatively prime, and a and c are relatively prime

Is the following statement true? if so prove it

(bc,a)=1

I computed a few examples, and i claim that it is true



Homework Equations



theorem: linear combination of gcd

if d = gcd(a,b)

then there exists integers u and v such that

d = au + bv

corollary:

(a,b)=1 if and only if 1 = au +bv


The Attempt at a Solution


From the corollary stated above, i claimed that we must show that

1 = (bc)u + (a)v

thus we must find integers u and v that satisfy the statement above

since (a,b) = 1 and (a,c) = 1, I used that corollary again,

1 = ax + by and 1 = af + cg
for some integers x,y,f, and g

and i am stuck at this point. I have no idea what i can do with these statements

I'm not sure if my approach is correct. But in the textbook, and in my class notes there are no examples showing how we can prove two integers are relatively prime. So i assumed this is how we approach the problem

the only other thing we have learned so far, is the divisibility algorithm, and division

any hints, guidance, would be appreciated. thanks

edit: possible solution

i see, that's the final step missing

i said since
(a,b) = 1 --> 1 = ax + by
(a,c) = 1 --> 1 = af + cg
By Theorem, x,y,f, and g exist

1 = 1.1 = (ax+by)(af+cg) = a^2xf + axcg + aabyf + bycg
= a(axf + xcg + byf) + bc(yg)
therefore let

u = axf + xcg + byf
and
v = yg

and since, all the "letters" used exist and are integers, they satisfy the domain, and the proposition

is that correct? even though "u" is messy, it doesn't matter right? because those integers exist (by theorem)
 
Last edited:

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,260
619
The easiest way to prove it is to use unique prime factorization. If gcd(a,b)=1 then a and b have no common prime factors. Ditto for a and c. The set of prime factors of bc is the union of the set of prime factors of b and c. If a has none in common with b and none in common with c, doesn't that prove it has none in common with bc?
 
Last edited:
  • #3
36
0
i see what you're saying and it makes sense

but we have not gone over that topic in class, and that was not introduced in any of the proofs in the book

even though that is the easiest way, is there another method to do so?

actually i skimmed through the book, and i see it's in the upcoming section

i doubt that my professor would allow me to use an idea from a chapter we will be discussing later
 
Last edited:
  • #4
36
0
what about this other approach: using the definition of GCD

d=gcd(a,b) if d satisfies the 2 following conditions

1) d|a and d|b
2) IF c|a and c|b --> c less than equal to d

1) is clearly true, since 1 divides any integer
2) i guess the hard part is to show that c is less than or equal to 1


Or I believe this is the correct approach

d = gcd(a,b) iff and only if d satisfies

1) d|a and d|b
2) if c|a and c|b --> c|d

nevermind, this last approach doesn't work, because by hypothesis, c neither divides a nor b
 
Last edited:
  • #5
Dick
Science Advisor
Homework Helper
26,260
619
Ok, gcd(a,b)=1 means that there are k1 and k2 such that k1*a+k2*b=1. gcd(a,c)=1 means there are l1 and l2 such that l1*a+l2*c=1. Multiply the two together and find m1 and m2 such that m1*a+m2*b*c=1.
 
Last edited:
  • #6
36
0
i see, that's the final step missing

i said since
(a,b) = 1 --> 1 = ax + by
(a,c) = 1 --> 1 = af + cg
By Theorem, x,y,f, and g exist

1 = 1.1 = (ax+by)(af+cg) = a^2xf + axcg + aabyf + bycg
= a(axf + xcg + byf) + bc(yg)
therefore let

u = axf + xcg + byf
and
v = yg

and since, all the "letters" used exist and are integers, they satisfy the domain, and the proposition

is that correct? even though "u" is messy, it doesn't matter right? because those integers exist (by theorem)
 
Last edited:
  • #7
Dick
Science Advisor
Homework Helper
26,260
619
That's correct. axf+xcg+byf is just as much of an integer as x is. It doesn't matter that it's "messy".
 

Related Threads on Abstract/Modern Algebra - Relatively Prime

Replies
5
Views
1K
Replies
3
Views
764
Replies
4
Views
2K
Replies
3
Views
2K
Replies
0
Views
924
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
11
Views
1K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
1
Views
876
  • Last Post
Replies
2
Views
2K
Top