Prime Divisor Problem

  • Thread starter scottstapp
  • Start date
  • #1
40
0

Homework Statement


I have to prove the following:
Let a1,a2, ...,an be integers and set b=a1*a2*...*an. If c is a nonzero integer and c is relatively prime to each ak, then c and b are relatively prime.


Homework Equations



Definition of relatively prime: Let a and b be integers, not both zero. if gcd(a,b)=1 then a and b are relatively prime.

The Attempt at a Solution



1. Let a1,a2, ...,an be integers and let b=a1*a2*...*an. Suppose there exists a nonzero integer c where c is relatively prime to each ak.

2. By defn, gcd(c,ak)=1

I need help showing that the gcd(c,a1*a2)=1

Thanks
 
Last edited:

Answers and Replies

  • #2
402
1
You don't need to suppose the existence of c; it is given by hyphotesis.

The best way to do this is to use induction on n and the following result (sometimes called Euclides' lemma): if c|ab and gcd(c,a)=1, then c|b.

If you haven't covered this lemma, argue like this: if gcd(c,a1*a2)>1, then there must be a common prime divisor p > 1 of c and a1*a2; p cannot divide a1 (because then gcd(a1,c)>1), so it must divide a2 and gcd(c,a2) > 1, and this is also impossible.
 
  • #3
40
0
I was just looking at Euclids Lemma actually and wondering how I would prove that c|ab? Is it because c is relatively prime with each a therefore it must divide ab?

Thank you for your help once again
 
Last edited:

Related Threads on Prime Divisor Problem

  • Last Post
Replies
19
Views
5K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
21
Views
2K
  • Last Post
Replies
24
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
881
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
4
Views
10K
Top