Proving the Theorem: (b,c)=1 implies (a,bc)=(a,b)(a,c) in Number Theory

In summary, we are trying to prove the theorem that if (b,c)=1, then (a,bc)=(a,b)(a,c). To prove this, we start by assuming that g=(a,b) and h=(a,c), and use the fact that g|a, g|b, h|a, and h|c. We then use these assumptions to show that (a,bc)=(a,b)(a,c). We also use the theorem of uniqueness of prime factorization, which we have proved previously, to help us in this proof. Finally, we conclude that (a,bc)=(a,b)(a,c) is indeed true.
  • #1
tennesseewiz
21
0

Homework Statement


Let a,b,c be integers. If (b,c)=1, then (a,bc)=(a,b)(a,c)

Homework Equations


This is difficult to answer because some theorems that we haven't proven yet, we can't use.

The Attempt at a Solution


Let g=(a,b) and h=(a,c), g and h are integers.
That means g|a and g|b, h|a and h|c.
That means:
a=gk, for some integer k
b=gq, for some integer q
a=hp for some integer p
c=ht for some integer t.

Multiply b and c together to get bc=(a,b)(a,c)qt. Then (a,bc)= (gk, (a,b)(a,c)qt), but that's as far as I got.
 
Physics news on Phys.org
  • #2
Sometimes it is just easier to think what things mean. Suppose that d divides a and bc. Think about the prime factors of d. Can you split them into two types? (Or is uniqueness of prime factorisation something you can't use?)
 
  • #3
Yeah, we can use uniqueness of prime factorization. We proved it last month, so that's why we can use it. I don't know how to do correct mathematical notation on the computer here, so hopefully you'll understand what I'm typing.

So d=(a,bc). d=(p1^r1)(p2^r2)(p3^r3)... or we can say d=(2^r2)(3^r3)(5^r5)... But I don't see how that's going to help me.
 
  • #4
So you know that gcd(a,b) is the product of the primes that divide a and b (with the right powers), similarly for gcd(a,c). And b and c are coprime so no primes divide both of them. Do you see where this is going?
 
  • #5
Theorem: If (b,c)=1, then (a,bc)=(a,b)(a,c).

Let g=(a,b) and h=(a,c), g and h are integers.
That means g|a and g|b, h|a and h|c.
Therefore:
b=qg, for some integer q.
c=th for some integer t.
g|b and h|c, and (b,c)=1, so (g,h)=1.
Therefore a=pgh, for some integer p.
(a,b)=g => (a,b)/g=1 => (pgh,qg)/g=1 => g(ph,q)/g=1 => (ph,q)=1 => (p,q)=1
(a,c)=h => (a,c)/h=1 => (pgh,th)/h=1 => h(pg,t)/h=1 => (pg,t)=1 => (p,t)=1
Therefore (p,qt)=1
(a,bc)=(pgh,qgth)=gh(p,qt)=gh*1=gh=(a,b)(a,c)
Therefore (a,bc)=(a,b)(a,c)
Q.E.D.

I've never done work like this before, so I'm sure I have several form issues, but I went ahead and showed as much of my thought process as I could in hopes that you understand. To the best of my knowledge, this proves the theorem, but if I took any liberties, please, feel free to correct me.
 

1. What is the definition of gcd in Number Theory?

The greatest common divisor (gcd) of two or more integers is the largest positive integer that divides each of the integers without leaving a remainder.

2. How do you find the gcd of two numbers using the Euclidean algorithm?

The Euclidean algorithm is a method for finding the gcd of two numbers. It involves repeatedly dividing the larger number by the smaller number and using the remainder as the new smaller number, until the remainder is zero. The last non-zero remainder is the gcd of the two numbers.

3. What is the relationship between the gcd and the lcm in Number Theory?

The least common multiple (lcm) of two or more integers is the smallest positive integer that is a multiple of all the integers. The gcd and lcm are related by the formula: gcd(a,b) * lcm(a,b) = a * b.

4. Can the gcd of three or more numbers be calculated using the Euclidean algorithm?

Yes, the Euclidean algorithm can be extended to find the gcd of three or more numbers. This involves finding the gcd of the first two numbers, then finding the gcd of that result and the third number, and so on until all numbers have been included.

5. How is the gcd used in solving Number Theory problems?

The gcd is a fundamental concept in Number Theory and is used in many problem-solving techniques. It can be used to simplify fractions, find common factors, and determine the number of prime factors in a given number. It is also used in advanced topics such as modular arithmetic and cryptography.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
465
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
150
  • Calculus and Beyond Homework Help
Replies
1
Views
414
  • Calculus and Beyond Homework Help
Replies
14
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
761
  • Calculus and Beyond Homework Help
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
811
Back
Top