(Removing all content from page) |
|||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| + | =[[HW1_MA453Fall2008walther|HW1]], Chapter 0, Problem 24, [[MA453]], Fall 2008, [[user:walther|Prof. Walther]]= | ||
| + | ==Problem Statement== | ||
| + | ''Could somebody please state the problem?'' | ||
| + | ---- | ||
| + | ==Discussion== | ||
| + | |||
| + | 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 | ||
| + | ---- | ||
| + | [[HW1_MA453Fall2008walther|Back to HW1]] | ||
| + | |||
| + | [[Main_Page_MA453Fall2008walther|Back to MA453 Fall 2008 Prof. Walther]] | ||
Latest revision as of 15:52, 22 October 2010
HW1, Chapter 0, Problem 24, MA453, Fall 2008, Prof. Walther
Problem Statement
Could somebody please state the problem?
Discussion
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
