Mixing
Proof of $5|p^2 implies 5|p$ for all $p in mathbbN$
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
One of the proofs that we've covered in class uses the fact that $5|p^2 implies 5|p$ where $p$ is a natural number. I've come up with a proof using the contrapositive, but was wondering if a direct proof exists.
elementary-number-theory
asked Jul 18 at 10:15
hazelmort
525
 |Â
show 1 more comment
up vote
0
down vote
favorite
One of the proofs that we've covered in class uses the fact that $5|p^2 implies 5|p$ where $p$ is a natural number. I've come up with a proof using the contrapositive, but was wondering if a direct proof exists.
elementary-number-theory
asked Jul 18 at 10:15
hazelmort
525
3
$5$ is a prime number, is that not enough?
– Trần Thúc Minh TrÃ
Jul 18 at 10:16
1
As @TrầnThúcMinhTrà says, you can simply use the fact that each factor in the prime factor decomposition of $p^2$ occurs at least twice.
– b00n heT
Jul 18 at 10:18
Something like that was mentioned in class, but I don't quite see how it follows
– hazelmort
Jul 18 at 10:18
If $5$ isn’t a prime factor of $p$ how can it be one of $p^2$?
– Michael Hoppe
Jul 18 at 10:20
1
Euclid's lemma:en.m.wikipedia.org/wiki/Euclid%27s_lemma
– Peter Szilas
Jul 18 at 10:34
 |Â
show 1 more comment
up vote
0
down vote
favorite
up vote
0
down vote
favorite
One of the proofs that we've covered in class uses the fact that $5|p^2 implies 5|p$ where $p$ is a natural number. I've come up with a proof using the contrapositive, but was wondering if a direct proof exists.
elementary-number-theory
asked Jul 18 at 10:15
hazelmort
525
One of the proofs that we've covered in class uses the fact that $5|p^2 implies 5|p$ where $p$ is a natural number. I've come up with a proof using the contrapositive, but was wondering if a direct proof exists.
elementary-number-theory
asked Jul 18 at 10:15
hazelmort
525
asked Jul 18 at 10:15
hazelmort
525
asked Jul 18 at 10:15
hazelmort
525
asked Jul 18 at 10:15
hazelmort
525
525
3
$5$ is a prime number, is that not enough?
– Trần Thúc Minh TrÃ
Jul 18 at 10:16
1
As @TrầnThúcMinhTrà says, you can simply use the fact that each factor in the prime factor decomposition of $p^2$ occurs at least twice.
– b00n heT
Jul 18 at 10:18
Something like that was mentioned in class, but I don't quite see how it follows
– hazelmort
Jul 18 at 10:18
If $5$ isn’t a prime factor of $p$ how can it be one of $p^2$?
– Michael Hoppe
Jul 18 at 10:20
1
Euclid's lemma:en.m.wikipedia.org/wiki/Euclid%27s_lemma
– Peter Szilas
Jul 18 at 10:34
 |Â
show 1 more comment
3
$5$ is a prime number, is that not enough?
– Trần Thúc Minh TrÃ
Jul 18 at 10:16
1
As @TrầnThúcMinhTrà says, you can simply use the fact that each factor in the prime factor decomposition of $p^2$ occurs at least twice.
– b00n heT
Jul 18 at 10:18
Something like that was mentioned in class, but I don't quite see how it follows
– hazelmort
Jul 18 at 10:18
If $5$ isn’t a prime factor of $p$ how can it be one of $p^2$?
– Michael Hoppe
Jul 18 at 10:20
1
Euclid's lemma:en.m.wikipedia.org/wiki/Euclid%27s_lemma
– Peter Szilas
Jul 18 at 10:34
3
3
$5$ is a prime number, is that not enough?
– Trần Thúc Minh TrÃ
Jul 18 at 10:16
$5$ is a prime number, is that not enough?
– Trần Thúc Minh TrÃ
Jul 18 at 10:16
1
1
As @TrầnThúcMinhTrà says, you can simply use the fact that each factor in the prime factor decomposition of $p^2$ occurs at least twice.
– b00n heT
Jul 18 at 10:18
As @TrầnThúcMinhTrà says, you can simply use the fact that each factor in the prime factor decomposition of $p^2$ occurs at least twice.
– b00n heT
Jul 18 at 10:18
Something like that was mentioned in class, but I don't quite see how it follows
– hazelmort
Jul 18 at 10:18
Something like that was mentioned in class, but I don't quite see how it follows
– hazelmort
Jul 18 at 10:18
If $5$ isn’t a prime factor of $p$ how can it be one of $p^2$?
– Michael Hoppe
Jul 18 at 10:20
If $5$ isn’t a prime factor of $p$ how can it be one of $p^2$?
– Michael Hoppe
Jul 18 at 10:20
1
1
Euclid's lemma:en.m.wikipedia.org/wiki/Euclid%27s_lemma
– Peter Szilas
Jul 18 at 10:34
Euclid's lemma:en.m.wikipedia.org/wiki/Euclid%27s_lemma
– Peter Szilas
Jul 18 at 10:34
 |Â
show 1 more comment
3 Answers
3
active
oldest
votes
up vote
3
down vote
(Expanding on my comment)
Hint: Consider the unique prime factor decomposition ($p_i$ are prime numbers, $n_iin mathbbN_>0$) of $p$
$$p=p_1^m_1cdotdotscdot p_n^m_n$$
then $p^2$'s prime factor decomposition is (why?)
$$p^2=p_1^2m_1cdotdotscdot p_n^2m_n$$
but if $5mid p^2$ then there exists $p_i=5$ (why?). Conclude.
answered Jul 18 at 10:22
b00n heT
7,99911430
add a comment |Â
up vote
1
down vote
Euclid's Lemma states that if a prime number $qmid ab$, then either $qmid a$ or $qmid b$. The only possible factorization of $p^2$ in this context sets $a=b=p$. Thus if $q=5$ divides $ab=p^2$, then either $5mid p(=a)$ or $5mid p(=b)$, in either case showing $5mid p$.
answered Jul 18 at 16:13
Keith Backman
45737
Apologies; I note after the fact that in the original question, $p$ is defined as a natural number, whereas I took $p$ to be a prime. Therefore, $a=b=p$ is not the only possible factorization of $p^2$. It is however, one possible factorization, and that adequately underpins the rest of the proof.
– Keith Backman
Jul 18 at 16:57
add a comment |Â
up vote
0
down vote
This is a direct application of Euclid's lemma that states if $q$ is prime and $q|ab$ then either $p|a$ or $p|b$. So if $5$, which is prime, divides $p^2 = p*p$ then either $5|p$ or .... $5|p$. So $5|p$.
======
If Euclid's Lemma is not intuitive obvious (which it should be if you play with it for a half an hour) then we can use the unique prime factorization that any natural number $p$ has a unique prime factorization $p =prod q_i^a_i$ where $q_i$ are the unique and distinct prime factors of $p$ then $p^2 = prod q_i^2a_i$ and the prime $5$ divides the product of primes $prod q_i^2a_i$ if and only if $5$ is one of the $q_i$. But that would mean $5$ divides $prod q_i^a_i = p$.
(But that's actually circular as we need Euclid's Lemma to prove the Unique Prime Factorization theorem in the first place.)
The direct proof of Euclid's Lemma is (to me) surprisingly difficult. Bezout's Identity says if $a$ and $b$ are natural numbers that have no factors in common then we can find $n$ and $m$ (one positive one negative) where $na + mb =1$. Bezout's Lemma is one of those surprising (to me) cases where a more advance concept, prime $q|jkimplies q|j$ or $q|k$, is much more obvious and intuitive (to me), that a more basic concept, that it is possible for $na + mb = 1$ (which to me is not obvious at all.)
Bezout's lemma is derived from Euclid's algorithm (not to be confused with Euclid's Lemma) that if:
$b > a$ then we can find $b = k*a + r; 0le r < a$ and as $b$ and $a$ have no factors in common then $a$ and $r$ can't have any factors in common either (because that factor would be a factor of $b$.)
So we can do it again and get $a = j*r + s$. .... and again to get $r = v*s + t$ and so on. As these numbers always get smaller this prosess must end with a $alpha = h*beta + 0$. But as $alpha$ and $beta$ have no prime factors in common it must be that $beta = 1$ (that's the only way $beta|alpha$ while being relatively prime to $alpha$.
So if you combine all those manipulations together to get back to the original values of $a,b$ you get an $na + mb = 1$.
Example: If $a = k*b +r$ and $a = j*r + s$ and $r = v*s + 1$ we can work backwards to get:
$1 = r - v*s = r - v*(a - j*r) = (a-k*b) - v*(a - j*(a-k*b)) = a - k*b - v*a + v*j*a - v*j*k*b= (1-v+vj)*a + (-k-vjk)*b$ so if $m = 1-v+vj$ and $n = -k-vjk$ then $ma + nb = 1$.
.....
Phew. So to use Bezout's Lemma to prove Euclid's Lemma that if $q$ is prime and $q|ab$ then either $q|a$ or $q|b$.
Pf: Assume $q|ab$ and $q$ is prime. If $q|a$ we are done. So let's assume $qnotmid a$. Then we want to prove it must be that $q|b$.
If $qnot mid a$ and $q$ is prime then $q$ and $a$ must have no common prime factors. So be Bezout's Lemma there exist $m,n$ so that
$nq + ma = 1$
So $nqb + mab = b$
But $q|ab$ so $ab = kq$ for some integer $k$.
So $nqb + m(ab) = nqb + m(kq) = q(nb + mk) = b$.
And $q|b$.
So that proves Euclid's lemma.
.....
The prime factorization theorem follows directly.
If $n = ab$ is composite you can factor $a$ and $b$ until you can't factor any further and then you will have a prime factorization. The only question is , is it unique. That is is it possible that $n = prod q_i$ and $n = prod r_j$ where $q_i $ and $r_i$ are prime (possibly repeated) but the $q_i$ and $r_j$ are different sets?
The answer is no. As $q_1|n = prod r_i$ so $q_1|r_j$ for some $r_j$. But $r_j$ is prime so $q_1 = r_j$. Then do the same thing with $frac nq_1 = prod_ine 2 q_i= prod_lne j r_l$.
Repeat until .... done.
======
That's a lot to learn in one sitting, but these should become universal truths in your mind as obvious as "The sky is blue".
Euclid's Lemma: If $q$ is prime and $q|ab$ then either $q|a$ or $q|b$.
Prime factorization theorem: Every natural number has a unique prime factorization where $n = q_1^a_1*....*q_n^a_n$ where $q_i$ are the unque prime factors of $n$.
Bezout's Lemma: If $gcd(a,b) = 1$ then there exist integers $n,m$ so that $na + mb = 1$.
Euclid's Algorithm: A method of finding those $m,n$ in Bezout's Lemma by successivley dividing and taking remainders and repeating until it ends.
answered Jul 18 at 17:00
fleablood
60.5k22575
Ooops, forgot to prove Euclid's Lemma! hold on a moment.
– fleablood
Jul 18 at 17:02
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
(Expanding on my comment)
Hint: Consider the unique prime factor decomposition ($p_i$ are prime numbers, $n_iin mathbbN_>0$) of $p$
$$p=p_1^m_1cdotdotscdot p_n^m_n$$
then $p^2$'s prime factor decomposition is (why?)
$$p^2=p_1^2m_1cdotdotscdot p_n^2m_n$$
but if $5mid p^2$ then there exists $p_i=5$ (why?). Conclude.
answered Jul 18 at 10:22
b00n heT
7,99911430
add a comment |Â
up vote
3
down vote
(Expanding on my comment)
Hint: Consider the unique prime factor decomposition ($p_i$ are prime numbers, $n_iin mathbbN_>0$) of $p$
$$p=p_1^m_1cdotdotscdot p_n^m_n$$
then $p^2$'s prime factor decomposition is (why?)
$$p^2=p_1^2m_1cdotdotscdot p_n^2m_n$$
but if $5mid p^2$ then there exists $p_i=5$ (why?). Conclude.
answered Jul 18 at 10:22
b00n heT
7,99911430
add a comment |Â
up vote
3
down vote
up vote
3
down vote
(Expanding on my comment)
Hint: Consider the unique prime factor decomposition ($p_i$ are prime numbers, $n_iin mathbbN_>0$) of $p$
$$p=p_1^m_1cdotdotscdot p_n^m_n$$
then $p^2$'s prime factor decomposition is (why?)
$$p^2=p_1^2m_1cdotdotscdot p_n^2m_n$$
but if $5mid p^2$ then there exists $p_i=5$ (why?). Conclude.
answered Jul 18 at 10:22
b00n heT
7,99911430
(Expanding on my comment)
Hint: Consider the unique prime factor decomposition ($p_i$ are prime numbers, $n_iin mathbbN_>0$) of $p$
$$p=p_1^m_1cdotdotscdot p_n^m_n$$
then $p^2$'s prime factor decomposition is (why?)
$$p^2=p_1^2m_1cdotdotscdot p_n^2m_n$$
but if $5mid p^2$ then there exists $p_i=5$ (why?). Conclude.
answered Jul 18 at 10:22
b00n heT
7,99911430
answered Jul 18 at 10:22
b00n heT
7,99911430
answered Jul 18 at 10:22
b00n heT
7,99911430
answered Jul 18 at 10:22
b00n heT
7,99911430
7,99911430
add a comment |Â
add a comment |Â
up vote
1
down vote
Euclid's Lemma states that if a prime number $qmid ab$, then either $qmid a$ or $qmid b$. The only possible factorization of $p^2$ in this context sets $a=b=p$. Thus if $q=5$ divides $ab=p^2$, then either $5mid p(=a)$ or $5mid p(=b)$, in either case showing $5mid p$.
answered Jul 18 at 16:13
Keith Backman
45737
Apologies; I note after the fact that in the original question, $p$ is defined as a natural number, whereas I took $p$ to be a prime. Therefore, $a=b=p$ is not the only possible factorization of $p^2$. It is however, one possible factorization, and that adequately underpins the rest of the proof.
– Keith Backman
Jul 18 at 16:57
add a comment |Â
up vote
1
down vote
Euclid's Lemma states that if a prime number $qmid ab$, then either $qmid a$ or $qmid b$. The only possible factorization of $p^2$ in this context sets $a=b=p$. Thus if $q=5$ divides $ab=p^2$, then either $5mid p(=a)$ or $5mid p(=b)$, in either case showing $5mid p$.
answered Jul 18 at 16:13
Keith Backman
45737
Apologies; I note after the fact that in the original question, $p$ is defined as a natural number, whereas I took $p$ to be a prime. Therefore, $a=b=p$ is not the only possible factorization of $p^2$. It is however, one possible factorization, and that adequately underpins the rest of the proof.
– Keith Backman
Jul 18 at 16:57
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Euclid's Lemma states that if a prime number $qmid ab$, then either $qmid a$ or $qmid b$. The only possible factorization of $p^2$ in this context sets $a=b=p$. Thus if $q=5$ divides $ab=p^2$, then either $5mid p(=a)$ or $5mid p(=b)$, in either case showing $5mid p$.
answered Jul 18 at 16:13
Keith Backman
45737
Euclid's Lemma states that if a prime number $qmid ab$, then either $qmid a$ or $qmid b$. The only possible factorization of $p^2$ in this context sets $a=b=p$. Thus if $q=5$ divides $ab=p^2$, then either $5mid p(=a)$ or $5mid p(=b)$, in either case showing $5mid p$.
answered Jul 18 at 16:13
Keith Backman
45737
answered Jul 18 at 16:13
Keith Backman
45737
answered Jul 18 at 16:13
Keith Backman
45737
answered Jul 18 at 16:13
Keith Backman
45737
45737
Apologies; I note after the fact that in the original question, $p$ is defined as a natural number, whereas I took $p$ to be a prime. Therefore, $a=b=p$ is not the only possible factorization of $p^2$. It is however, one possible factorization, and that adequately underpins the rest of the proof.
– Keith Backman
Jul 18 at 16:57
add a comment |Â
Apologies; I note after the fact that in the original question, $p$ is defined as a natural number, whereas I took $p$ to be a prime. Therefore, $a=b=p$ is not the only possible factorization of $p^2$. It is however, one possible factorization, and that adequately underpins the rest of the proof.
– Keith Backman
Jul 18 at 16:57
Apologies; I note after the fact that in the original question, $p$ is defined as a natural number, whereas I took $p$ to be a prime. Therefore, $a=b=p$ is not the only possible factorization of $p^2$. It is however, one possible factorization, and that adequately underpins the rest of the proof.
– Keith Backman
Jul 18 at 16:57
Apologies; I note after the fact that in the original question, $p$ is defined as a natural number, whereas I took $p$ to be a prime. Therefore, $a=b=p$ is not the only possible factorization of $p^2$. It is however, one possible factorization, and that adequately underpins the rest of the proof.
– Keith Backman
Jul 18 at 16:57
add a comment |Â
up vote
0
down vote
This is a direct application of Euclid's lemma that states if $q$ is prime and $q|ab$ then either $p|a$ or $p|b$. So if $5$, which is prime, divides $p^2 = p*p$ then either $5|p$ or .... $5|p$. So $5|p$.
======
If Euclid's Lemma is not intuitive obvious (which it should be if you play with it for a half an hour) then we can use the unique prime factorization that any natural number $p$ has a unique prime factorization $p =prod q_i^a_i$ where $q_i$ are the unique and distinct prime factors of $p$ then $p^2 = prod q_i^2a_i$ and the prime $5$ divides the product of primes $prod q_i^2a_i$ if and only if $5$ is one of the $q_i$. But that would mean $5$ divides $prod q_i^a_i = p$.
(But that's actually circular as we need Euclid's Lemma to prove the Unique Prime Factorization theorem in the first place.)
The direct proof of Euclid's Lemma is (to me) surprisingly difficult. Bezout's Identity says if $a$ and $b$ are natural numbers that have no factors in common then we can find $n$ and $m$ (one positive one negative) where $na + mb =1$. Bezout's Lemma is one of those surprising (to me) cases where a more advance concept, prime $q|jkimplies q|j$ or $q|k$, is much more obvious and intuitive (to me), that a more basic concept, that it is possible for $na + mb = 1$ (which to me is not obvious at all.)
Bezout's lemma is derived from Euclid's algorithm (not to be confused with Euclid's Lemma) that if:
$b > a$ then we can find $b = k*a + r; 0le r < a$ and as $b$ and $a$ have no factors in common then $a$ and $r$ can't have any factors in common either (because that factor would be a factor of $b$.)
So we can do it again and get $a = j*r + s$. .... and again to get $r = v*s + t$ and so on. As these numbers always get smaller this prosess must end with a $alpha = h*beta + 0$. But as $alpha$ and $beta$ have no prime factors in common it must be that $beta = 1$ (that's the only way $beta|alpha$ while being relatively prime to $alpha$.
So if you combine all those manipulations together to get back to the original values of $a,b$ you get an $na + mb = 1$.
Example: If $a = k*b +r$ and $a = j*r + s$ and $r = v*s + 1$ we can work backwards to get:
$1 = r - v*s = r - v*(a - j*r) = (a-k*b) - v*(a - j*(a-k*b)) = a - k*b - v*a + v*j*a - v*j*k*b= (1-v+vj)*a + (-k-vjk)*b$ so if $m = 1-v+vj$ and $n = -k-vjk$ then $ma + nb = 1$.
.....
Phew. So to use Bezout's Lemma to prove Euclid's Lemma that if $q$ is prime and $q|ab$ then either $q|a$ or $q|b$.
Pf: Assume $q|ab$ and $q$ is prime. If $q|a$ we are done. So let's assume $qnotmid a$. Then we want to prove it must be that $q|b$.
If $qnot mid a$ and $q$ is prime then $q$ and $a$ must have no common prime factors. So be Bezout's Lemma there exist $m,n$ so that
$nq + ma = 1$
So $nqb + mab = b$
But $q|ab$ so $ab = kq$ for some integer $k$.
So $nqb + m(ab) = nqb + m(kq) = q(nb + mk) = b$.
And $q|b$.
So that proves Euclid's lemma.
.....
The prime factorization theorem follows directly.
If $n = ab$ is composite you can factor $a$ and $b$ until you can't factor any further and then you will have a prime factorization. The only question is , is it unique. That is is it possible that $n = prod q_i$ and $n = prod r_j$ where $q_i $ and $r_i$ are prime (possibly repeated) but the $q_i$ and $r_j$ are different sets?
The answer is no. As $q_1|n = prod r_i$ so $q_1|r_j$ for some $r_j$. But $r_j$ is prime so $q_1 = r_j$. Then do the same thing with $frac nq_1 = prod_ine 2 q_i= prod_lne j r_l$.
Repeat until .... done.
======
That's a lot to learn in one sitting, but these should become universal truths in your mind as obvious as "The sky is blue".
Euclid's Lemma: If $q$ is prime and $q|ab$ then either $q|a$ or $q|b$.
Prime factorization theorem: Every natural number has a unique prime factorization where $n = q_1^a_1*....*q_n^a_n$ where $q_i$ are the unque prime factors of $n$.
Bezout's Lemma: If $gcd(a,b) = 1$ then there exist integers $n,m$ so that $na + mb = 1$.
Euclid's Algorithm: A method of finding those $m,n$ in Bezout's Lemma by successivley dividing and taking remainders and repeating until it ends.
answered Jul 18 at 17:00
fleablood
60.5k22575
Ooops, forgot to prove Euclid's Lemma! hold on a moment.
– fleablood
Jul 18 at 17:02
add a comment |Â
up vote
0
down vote
This is a direct application of Euclid's lemma that states if $q$ is prime and $q|ab$ then either $p|a$ or $p|b$. So if $5$, which is prime, divides $p^2 = p*p$ then either $5|p$ or .... $5|p$. So $5|p$.
======
If Euclid's Lemma is not intuitive obvious (which it should be if you play with it for a half an hour) then we can use the unique prime factorization that any natural number $p$ has a unique prime factorization $p =prod q_i^a_i$ where $q_i$ are the unique and distinct prime factors of $p$ then $p^2 = prod q_i^2a_i$ and the prime $5$ divides the product of primes $prod q_i^2a_i$ if and only if $5$ is one of the $q_i$. But that would mean $5$ divides $prod q_i^a_i = p$.
(But that's actually circular as we need Euclid's Lemma to prove the Unique Prime Factorization theorem in the first place.)
The direct proof of Euclid's Lemma is (to me) surprisingly difficult. Bezout's Identity says if $a$ and $b$ are natural numbers that have no factors in common then we can find $n$ and $m$ (one positive one negative) where $na + mb =1$. Bezout's Lemma is one of those surprising (to me) cases where a more advance concept, prime $q|jkimplies q|j$ or $q|k$, is much more obvious and intuitive (to me), that a more basic concept, that it is possible for $na + mb = 1$ (which to me is not obvious at all.)
Bezout's lemma is derived from Euclid's algorithm (not to be confused with Euclid's Lemma) that if:
$b > a$ then we can find $b = k*a + r; 0le r < a$ and as $b$ and $a$ have no factors in common then $a$ and $r$ can't have any factors in common either (because that factor would be a factor of $b$.)
So we can do it again and get $a = j*r + s$. .... and again to get $r = v*s + t$ and so on. As these numbers always get smaller this prosess must end with a $alpha = h*beta + 0$. But as $alpha$ and $beta$ have no prime factors in common it must be that $beta = 1$ (that's the only way $beta|alpha$ while being relatively prime to $alpha$.
So if you combine all those manipulations together to get back to the original values of $a,b$ you get an $na + mb = 1$.
Example: If $a = k*b +r$ and $a = j*r + s$ and $r = v*s + 1$ we can work backwards to get:
$1 = r - v*s = r - v*(a - j*r) = (a-k*b) - v*(a - j*(a-k*b)) = a - k*b - v*a + v*j*a - v*j*k*b= (1-v+vj)*a + (-k-vjk)*b$ so if $m = 1-v+vj$ and $n = -k-vjk$ then $ma + nb = 1$.
.....
Phew. So to use Bezout's Lemma to prove Euclid's Lemma that if $q$ is prime and $q|ab$ then either $q|a$ or $q|b$.
Pf: Assume $q|ab$ and $q$ is prime. If $q|a$ we are done. So let's assume $qnotmid a$. Then we want to prove it must be that $q|b$.
If $qnot mid a$ and $q$ is prime then $q$ and $a$ must have no common prime factors. So be Bezout's Lemma there exist $m,n$ so that
$nq + ma = 1$
So $nqb + mab = b$
But $q|ab$ so $ab = kq$ for some integer $k$.
So $nqb + m(ab) = nqb + m(kq) = q(nb + mk) = b$.
And $q|b$.
So that proves Euclid's lemma.
.....
The prime factorization theorem follows directly.
If $n = ab$ is composite you can factor $a$ and $b$ until you can't factor any further and then you will have a prime factorization. The only question is , is it unique. That is is it possible that $n = prod q_i$ and $n = prod r_j$ where $q_i $ and $r_i$ are prime (possibly repeated) but the $q_i$ and $r_j$ are different sets?
The answer is no. As $q_1|n = prod r_i$ so $q_1|r_j$ for some $r_j$. But $r_j$ is prime so $q_1 = r_j$. Then do the same thing with $frac nq_1 = prod_ine 2 q_i= prod_lne j r_l$.
Repeat until .... done.
======
That's a lot to learn in one sitting, but these should become universal truths in your mind as obvious as "The sky is blue".
Euclid's Lemma: If $q$ is prime and $q|ab$ then either $q|a$ or $q|b$.
Prime factorization theorem: Every natural number has a unique prime factorization where $n = q_1^a_1*....*q_n^a_n$ where $q_i$ are the unque prime factors of $n$.
Bezout's Lemma: If $gcd(a,b) = 1$ then there exist integers $n,m$ so that $na + mb = 1$.
Euclid's Algorithm: A method of finding those $m,n$ in Bezout's Lemma by successivley dividing and taking remainders and repeating until it ends.
answered Jul 18 at 17:00
fleablood
60.5k22575
Ooops, forgot to prove Euclid's Lemma! hold on a moment.
– fleablood
Jul 18 at 17:02
add a comment |Â
up vote
0
down vote
up vote
0
down vote
This is a direct application of Euclid's lemma that states if $q$ is prime and $q|ab$ then either $p|a$ or $p|b$. So if $5$, which is prime, divides $p^2 = p*p$ then either $5|p$ or .... $5|p$. So $5|p$.
======
If Euclid's Lemma is not intuitive obvious (which it should be if you play with it for a half an hour) then we can use the unique prime factorization that any natural number $p$ has a unique prime factorization $p =prod q_i^a_i$ where $q_i$ are the unique and distinct prime factors of $p$ then $p^2 = prod q_i^2a_i$ and the prime $5$ divides the product of primes $prod q_i^2a_i$ if and only if $5$ is one of the $q_i$. But that would mean $5$ divides $prod q_i^a_i = p$.
(But that's actually circular as we need Euclid's Lemma to prove the Unique Prime Factorization theorem in the first place.)
The direct proof of Euclid's Lemma is (to me) surprisingly difficult. Bezout's Identity says if $a$ and $b$ are natural numbers that have no factors in common then we can find $n$ and $m$ (one positive one negative) where $na + mb =1$. Bezout's Lemma is one of those surprising (to me) cases where a more advance concept, prime $q|jkimplies q|j$ or $q|k$, is much more obvious and intuitive (to me), that a more basic concept, that it is possible for $na + mb = 1$ (which to me is not obvious at all.)
Bezout's lemma is derived from Euclid's algorithm (not to be confused with Euclid's Lemma) that if:
$b > a$ then we can find $b = k*a + r; 0le r < a$ and as $b$ and $a$ have no factors in common then $a$ and $r$ can't have any factors in common either (because that factor would be a factor of $b$.)
So we can do it again and get $a = j*r + s$. .... and again to get $r = v*s + t$ and so on. As these numbers always get smaller this prosess must end with a $alpha = h*beta + 0$. But as $alpha$ and $beta$ have no prime factors in common it must be that $beta = 1$ (that's the only way $beta|alpha$ while being relatively prime to $alpha$.
So if you combine all those manipulations together to get back to the original values of $a,b$ you get an $na + mb = 1$.
Example: If $a = k*b +r$ and $a = j*r + s$ and $r = v*s + 1$ we can work backwards to get:
$1 = r - v*s = r - v*(a - j*r) = (a-k*b) - v*(a - j*(a-k*b)) = a - k*b - v*a + v*j*a - v*j*k*b= (1-v+vj)*a + (-k-vjk)*b$ so if $m = 1-v+vj$ and $n = -k-vjk$ then $ma + nb = 1$.
.....
Phew. So to use Bezout's Lemma to prove Euclid's Lemma that if $q$ is prime and $q|ab$ then either $q|a$ or $q|b$.
Pf: Assume $q|ab$ and $q$ is prime. If $q|a$ we are done. So let's assume $qnotmid a$. Then we want to prove it must be that $q|b$.
If $qnot mid a$ and $q$ is prime then $q$ and $a$ must have no common prime factors. So be Bezout's Lemma there exist $m,n$ so that
$nq + ma = 1$
So $nqb + mab = b$
But $q|ab$ so $ab = kq$ for some integer $k$.
So $nqb + m(ab) = nqb + m(kq) = q(nb + mk) = b$.
And $q|b$.
So that proves Euclid's lemma.
.....
The prime factorization theorem follows directly.
If $n = ab$ is composite you can factor $a$ and $b$ until you can't factor any further and then you will have a prime factorization. The only question is , is it unique. That is is it possible that $n = prod q_i$ and $n = prod r_j$ where $q_i $ and $r_i$ are prime (possibly repeated) but the $q_i$ and $r_j$ are different sets?
The answer is no. As $q_1|n = prod r_i$ so $q_1|r_j$ for some $r_j$. But $r_j$ is prime so $q_1 = r_j$. Then do the same thing with $frac nq_1 = prod_ine 2 q_i= prod_lne j r_l$.
Repeat until .... done.
======
That's a lot to learn in one sitting, but these should become universal truths in your mind as obvious as "The sky is blue".
Euclid's Lemma: If $q$ is prime and $q|ab$ then either $q|a$ or $q|b$.
Prime factorization theorem: Every natural number has a unique prime factorization where $n = q_1^a_1*....*q_n^a_n$ where $q_i$ are the unque prime factors of $n$.
Bezout's Lemma: If $gcd(a,b) = 1$ then there exist integers $n,m$ so that $na + mb = 1$.
Euclid's Algorithm: A method of finding those $m,n$ in Bezout's Lemma by successivley dividing and taking remainders and repeating until it ends.
answered Jul 18 at 17:00
fleablood
60.5k22575
This is a direct application of Euclid's lemma that states if $q$ is prime and $q|ab$ then either $p|a$ or $p|b$. So if $5$, which is prime, divides $p^2 = p*p$ then either $5|p$ or .... $5|p$. So $5|p$.
======
If Euclid's Lemma is not intuitive obvious (which it should be if you play with it for a half an hour) then we can use the unique prime factorization that any natural number $p$ has a unique prime factorization $p =prod q_i^a_i$ where $q_i$ are the unique and distinct prime factors of $p$ then $p^2 = prod q_i^2a_i$ and the prime $5$ divides the product of primes $prod q_i^2a_i$ if and only if $5$ is one of the $q_i$. But that would mean $5$ divides $prod q_i^a_i = p$.
(But that's actually circular as we need Euclid's Lemma to prove the Unique Prime Factorization theorem in the first place.)
The direct proof of Euclid's Lemma is (to me) surprisingly difficult. Bezout's Identity says if $a$ and $b$ are natural numbers that have no factors in common then we can find $n$ and $m$ (one positive one negative) where $na + mb =1$. Bezout's Lemma is one of those surprising (to me) cases where a more advance concept, prime $q|jkimplies q|j$ or $q|k$, is much more obvious and intuitive (to me), that a more basic concept, that it is possible for $na + mb = 1$ (which to me is not obvious at all.)
Bezout's lemma is derived from Euclid's algorithm (not to be confused with Euclid's Lemma) that if:
$b > a$ then we can find $b = k*a + r; 0le r < a$ and as $b$ and $a$ have no factors in common then $a$ and $r$ can't have any factors in common either (because that factor would be a factor of $b$.)
So we can do it again and get $a = j*r + s$. .... and again to get $r = v*s + t$ and so on. As these numbers always get smaller this prosess must end with a $alpha = h*beta + 0$. But as $alpha$ and $beta$ have no prime factors in common it must be that $beta = 1$ (that's the only way $beta|alpha$ while being relatively prime to $alpha$.
So if you combine all those manipulations together to get back to the original values of $a,b$ you get an $na + mb = 1$.
Example: If $a = k*b +r$ and $a = j*r + s$ and $r = v*s + 1$ we can work backwards to get:
$1 = r - v*s = r - v*(a - j*r) = (a-k*b) - v*(a - j*(a-k*b)) = a - k*b - v*a + v*j*a - v*j*k*b= (1-v+vj)*a + (-k-vjk)*b$ so if $m = 1-v+vj$ and $n = -k-vjk$ then $ma + nb = 1$.
.....
Phew. So to use Bezout's Lemma to prove Euclid's Lemma that if $q$ is prime and $q|ab$ then either $q|a$ or $q|b$.
Pf: Assume $q|ab$ and $q$ is prime. If $q|a$ we are done. So let's assume $qnotmid a$. Then we want to prove it must be that $q|b$.
If $qnot mid a$ and $q$ is prime then $q$ and $a$ must have no common prime factors. So be Bezout's Lemma there exist $m,n$ so that
$nq + ma = 1$
So $nqb + mab = b$
But $q|ab$ so $ab = kq$ for some integer $k$.
So $nqb + m(ab) = nqb + m(kq) = q(nb + mk) = b$.
And $q|b$.
So that proves Euclid's lemma.
.....
The prime factorization theorem follows directly.
If $n = ab$ is composite you can factor $a$ and $b$ until you can't factor any further and then you will have a prime factorization. The only question is , is it unique. That is is it possible that $n = prod q_i$ and $n = prod r_j$ where $q_i $ and $r_i$ are prime (possibly repeated) but the $q_i$ and $r_j$ are different sets?
The answer is no. As $q_1|n = prod r_i$ so $q_1|r_j$ for some $r_j$. But $r_j$ is prime so $q_1 = r_j$. Then do the same thing with $frac nq_1 = prod_ine 2 q_i= prod_lne j r_l$.
Repeat until .... done.
======
That's a lot to learn in one sitting, but these should become universal truths in your mind as obvious as "The sky is blue".
Euclid's Lemma: If $q$ is prime and $q|ab$ then either $q|a$ or $q|b$.
Prime factorization theorem: Every natural number has a unique prime factorization where $n = q_1^a_1*....*q_n^a_n$ where $q_i$ are the unque prime factors of $n$.
Bezout's Lemma: If $gcd(a,b) = 1$ then there exist integers $n,m$ so that $na + mb = 1$.
Euclid's Algorithm: A method of finding those $m,n$ in Bezout's Lemma by successivley dividing and taking remainders and repeating until it ends.
answered Jul 18 at 17:00
fleablood
60.5k22575
edited Jul 18 at 17:25
answered Jul 18 at 17:00
fleablood
60.5k22575
answered Jul 18 at 17:00
fleablood
60.5k22575
answered Jul 18 at 17:00
fleablood
60.5k22575
60.5k22575
Ooops, forgot to prove Euclid's Lemma! hold on a moment.
– fleablood
Jul 18 at 17:02
add a comment |Â
Ooops, forgot to prove Euclid's Lemma! hold on a moment.
– fleablood
Jul 18 at 17:02
Ooops, forgot to prove Euclid's Lemma! hold on a moment.
– fleablood
Jul 18 at 17:02
Ooops, forgot to prove Euclid's Lemma! hold on a moment.
– fleablood
Jul 18 at 17:02
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2855438%2fproof-of-5p2-implies-5p-for-all-p-in-mathbbn%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
3
$5$ is a prime number, is that not enough?
– Trần Thúc Minh TrÃ
Jul 18 at 10:16
1
As @TrầnThúcMinhTrà says, you can simply use the fact that each factor in the prime factor decomposition of $p^2$ occurs at least twice.
– b00n heT
Jul 18 at 10:18
Something like that was mentioned in class, but I don't quite see how it follows
– hazelmort
Jul 18 at 10:18
If $5$ isn’t a prime factor of $p$ how can it be one of $p^2$?
– Michael Hoppe
Jul 18 at 10:20
1
Euclid's lemma:en.m.wikipedia.org/wiki/Euclid%27s_lemma
– Peter Szilas
Jul 18 at 10:34