pairwise prime

• Sep 6th 2008, 01:04 PM
rmpatel5
pairwise prime
Let a,a2,...,an chttp://answerboard.cramster.com/Answ...9933404064.gif with a1, a2,...,an pairwise relatively prime. Prove that if ai http://answerboard.cramster.com/answ...32a2bb79e9.jpg c for each i, then a1,a2,...an http://answerboard.cramster.com/imag...32a2bb79e9.jpg c

so far:
gcd(a1,a2,an)=1 since its pairwise then gcd (a1,an) =1, gcd (a2,an)=1
gcd(ai,aj)=1

c=ai*m
• Sep 6th 2008, 01:13 PM
Laurent
I'd suggest you to procede by induction.

Show that if \$\displaystyle a_1\cdots a_k|c\$, then \$\displaystyle a_1\cdots a_ka_{k+1}|c\$. Hint: remark that \$\displaystyle a_1\cdots a_k\$ and \$\displaystyle a_{k+1}\$ are relatively prime (this by the way could be proved by induction).
• Sep 6th 2008, 01:51 PM
rmpatel5
Quote:

Originally Posted by Laurent
I'd suggest you to procede by induction.

Show that if \$\displaystyle a_1\cdots a_k|c\$, then \$\displaystyle a_1\cdots a_ka_{k+1}|c\$. Hint: remark that \$\displaystyle a_1\cdots a_k\$ and \$\displaystyle a_{k+1}\$ are relatively prime (this by the way could be proved by induction).

Hey no clue if i did this right but does it go something like this??

f(k)=a1....ak
f(k+1)=a1....ak,ak+1
f(k+1)-f(k)=a1....ak,ak+1-a1....ak
=a1....ak(ak+1-1)
=a1....ak(ak)
• Sep 6th 2008, 02:54 PM
rmpatel5
suppose a,c are relatively prime. i.e. (a,c) = 1. also, a| bc ==> a p = bc for some integer p*. so, by Euclidean algorithm, there exists x and y integers such that 1 = ax+ cy
multiplying b we get b = (ab)x + (bc)y
==> b = a(bx) + (ap)y by *
==> b = a(bx+py) .
while b,x,p,y are integers we have bx+py is an integer and so, b is an integral mulple of a.
==> a | b.
basing on this result, we go to the actual question.
a1 | c , a2 |c , a1 and a2 are reletively prime.
so, a1.a2 | c
extending this property for n integers we get a1.a2.---.an | c.

can i do it this way?
• Sep 6th 2008, 04:52 PM
ThePerfectHacker
Use the recommendation of Laurent.

We just need to prove that if \$\displaystyle \gcd(a,b)=1\$ and \$\displaystyle a|c,b|c\$ then \$\displaystyle ab|c\$.

Since \$\displaystyle a|c,b|c\$ it means \$\displaystyle aa'=c,bb'=c\$.

Now \$\displaystyle \gcd(a,b)=1\implies 1 = ax+by \implies c = acx+bcy \implies c = abb'cx+aa'bcy\$.

Factor out \$\displaystyle ab\$ to complete the proof.
• Sep 6th 2008, 05:21 PM
rmpatel5
Quote:

Originally Posted by ThePerfectHacker
Use the recommendation of Laurent.

We just need to prove that if \$\displaystyle \gcd(a,b)=1\$ and \$\displaystyle a|c,b|c\$ then \$\displaystyle ab|c\$.

Since \$\displaystyle a|c,b|c\$ it means \$\displaystyle aa'=c,bb'=c\$.

Now \$\displaystyle \gcd(a,b)=1\implies 1 = ax+by \implies c = acx+bcy \implies c = abb'cx+aa'bcy\$.

Factor out \$\displaystyle ab\$ to complete the proof.

I am really lost to what your trying to do. You say to use Laurent recommendation, but you use a different proof. I know how to do the proof you did as it was required for one of our hw problems, but i dont see how solves this question of mines. Also, does my proof in the early post work?