(Removing all content from page) |
|||
| Line 1: | Line 1: | ||
| + | Let a<sub>1</sub>=a<sub>1</sub> and a<sub>2</sub>a<sub>3</sub>...a<sub>n</sub>=b<sub>1</sub> | ||
| + | If p is a prime and divides a<sub>1</sub>a<sub>2</sub>a<sub>3</sub>...a<sub>n</sub>, then p divides a<sub>1</sub>b<sub>1</sub> | ||
| + | |||
| + | If p is a prime that divides a<sub>1</sub>b<sub>1</sub>, then p divides a<sub>1</sub> or b<sub>1</sub> | ||
| + | |||
| + | Let's say p does not divide a<sub>1</sub>, then gcd(p,a<sub>1</sub>)=1 | ||
| + | |||
| + | This means that there exists x and y for which the equation xp+ya<sub>1</sub>=1 holds | ||
| + | |||
| + | Let's multiply both sides of this equation by b<sub>1</sub>: | ||
| + | |||
| + | xpb<sub>1</sub>+ya<sub>1</sub>b<sub>1</sub>=b<sub>1</sub> | ||
| + | |||
| + | By induction, p divides a<sub>1</sub>b<sub>1</sub> and let a<sub>1</sub>b<sub>1</sub>=kp. Let's divide the equation above by p: | ||
| + | |||
| + | xb<sub>1</sub>+yk=b<sub>1</sub>/p | ||
| + | |||
| + | If the LHS of the equation can be divided by p, the RHS of the equation can be divided by p also. Then, b<sub>1</sub> can be divided by p. | ||
| + | |||
| + | Next, we let b<sub>2</sub>=a<sub>3</sub>a<sub>4</sub>...a<sub>n</sub> and repeat the process above. Eventually, we will find the a<sub>i</sub> for some i, which can be divided by p. | ||
| + | |||
| + | -Ozgur | ||
Revision as of 12:43, 7 September 2008
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
