Revision as of 13:43, 7 September 2008 by Odelemen (Talk)

Let a1=a1 and a2a3...an=b1

If p is a prime and divides a1a2a3...an, then p divides a1b1

If p is a prime that divides a1b1, then p divides a1 or b1

Let's say p does not divide a1, then gcd(p,a1)=1

This means that there exists x and y for which the equation xp+ya1=1 holds

Let's multiply both sides of this equation by b1:

xpb1+ya1b1=b1

By induction, p divides a1b1 and let a1b1=kp. Let's divide the equation above by p:

xb1+yk=b1/p

If the LHS of the equation can be divided by p, the RHS of the equation can be divided by p also. Then, b1 can be divided by p.

Next, we let b2=a3a4...an and repeat the process above. Eventually, we will find the ai for some i, which can be divided by p.

-Ozgur

Alumni Liaison

Ph.D. 2007, working on developing cool imaging technologies for digital cameras, camera phones, and video surveillance cameras.

Buyue Zhang