Mixing
$a^2−ab+b^2=c^2$. Show prime factors of $c$ are of the form $6k + 1$
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I encountered this question in Number Theory by Naoki Sato.
Let a, b, and c be positive integers that are pairwise relatively prime,
and that satisfy $a^2−ab+b^2=c^2$. Show that every prime factor of c is
of the form $6k + 1$.
Attempt:
Since primes are either of the form $6k+1$ or $6k-1$, I tried to show $p equiv 1 pmod6$ by showing $p equiv 1 pmod2$ and $p equiv 1 pmod3$ but I am unable to show $p equiv 1 pmod3$.
Another direction I tried was to assume there exist a prime factor $p$ of $c$ with $p=6k-1$.
By brute force I know that $a^2−ab+b^2 equiv 0, 1, 3$, or $4 pmod6$ but I can't see how to get a contradiction from here.
I am not sure how to use the condition that all 3 numbers are pairwise coprime.
Any help is much appreciated!
number-theory
asked Jul 18 at 16:53
eatfood
452
add a comment |Â
up vote
2
down vote
favorite
I encountered this question in Number Theory by Naoki Sato.
Let a, b, and c be positive integers that are pairwise relatively prime,
and that satisfy $a^2−ab+b^2=c^2$. Show that every prime factor of c is
of the form $6k + 1$.
Attempt:
Since primes are either of the form $6k+1$ or $6k-1$, I tried to show $p equiv 1 pmod6$ by showing $p equiv 1 pmod2$ and $p equiv 1 pmod3$ but I am unable to show $p equiv 1 pmod3$.
Another direction I tried was to assume there exist a prime factor $p$ of $c$ with $p=6k-1$.
By brute force I know that $a^2−ab+b^2 equiv 0, 1, 3$, or $4 pmod6$ but I can't see how to get a contradiction from here.
I am not sure how to use the condition that all 3 numbers are pairwise coprime.
Any help is much appreciated!
number-theory
asked Jul 18 at 16:53
eatfood
452
1
math.stackexchange.com/questions/1351994/…
– individ
Jul 18 at 17:00
2
Have you ever seen the "Gaussian" proofs that if $a^2+b^2=c$ and $a, b, c$ are relatively prime, then all prime factors of $c$ are of the form $4k+1$? This operates on very similar principles using a different ring of integers.
– Steven Stadnicki
Jul 18 at 17:00
@individ thanks for the link! ill check it out
– eatfood
Jul 19 at 3:19
@StevenStadnicki no I haven't, I have only just started on learning number theory, and some of the proofs seem very difficult to come up with
– eatfood
Jul 19 at 3:20
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I encountered this question in Number Theory by Naoki Sato.
Let a, b, and c be positive integers that are pairwise relatively prime,
and that satisfy $a^2−ab+b^2=c^2$. Show that every prime factor of c is
of the form $6k + 1$.
Attempt:
Since primes are either of the form $6k+1$ or $6k-1$, I tried to show $p equiv 1 pmod6$ by showing $p equiv 1 pmod2$ and $p equiv 1 pmod3$ but I am unable to show $p equiv 1 pmod3$.
Another direction I tried was to assume there exist a prime factor $p$ of $c$ with $p=6k-1$.
By brute force I know that $a^2−ab+b^2 equiv 0, 1, 3$, or $4 pmod6$ but I can't see how to get a contradiction from here.
I am not sure how to use the condition that all 3 numbers are pairwise coprime.
Any help is much appreciated!
number-theory
asked Jul 18 at 16:53
eatfood
452
I encountered this question in Number Theory by Naoki Sato.
Let a, b, and c be positive integers that are pairwise relatively prime,
and that satisfy $a^2−ab+b^2=c^2$. Show that every prime factor of c is
of the form $6k + 1$.
Attempt:
Since primes are either of the form $6k+1$ or $6k-1$, I tried to show $p equiv 1 pmod6$ by showing $p equiv 1 pmod2$ and $p equiv 1 pmod3$ but I am unable to show $p equiv 1 pmod3$.
Another direction I tried was to assume there exist a prime factor $p$ of $c$ with $p=6k-1$.
By brute force I know that $a^2−ab+b^2 equiv 0, 1, 3$, or $4 pmod6$ but I can't see how to get a contradiction from here.
I am not sure how to use the condition that all 3 numbers are pairwise coprime.
Any help is much appreciated!
number-theory
asked Jul 18 at 16:53
eatfood
452
asked Jul 18 at 16:53
eatfood
452
asked Jul 18 at 16:53
eatfood
452
asked Jul 18 at 16:53
eatfood
452
452
1
math.stackexchange.com/questions/1351994/…
– individ
Jul 18 at 17:00
2
Have you ever seen the "Gaussian" proofs that if $a^2+b^2=c$ and $a, b, c$ are relatively prime, then all prime factors of $c$ are of the form $4k+1$? This operates on very similar principles using a different ring of integers.
– Steven Stadnicki
Jul 18 at 17:00
@individ thanks for the link! ill check it out
– eatfood
Jul 19 at 3:19
@StevenStadnicki no I haven't, I have only just started on learning number theory, and some of the proofs seem very difficult to come up with
– eatfood
Jul 19 at 3:20
add a comment |Â
1
math.stackexchange.com/questions/1351994/…
– individ
Jul 18 at 17:00
2
Have you ever seen the "Gaussian" proofs that if $a^2+b^2=c$ and $a, b, c$ are relatively prime, then all prime factors of $c$ are of the form $4k+1$? This operates on very similar principles using a different ring of integers.
– Steven Stadnicki
Jul 18 at 17:00
@individ thanks for the link! ill check it out
– eatfood
Jul 19 at 3:19
@StevenStadnicki no I haven't, I have only just started on learning number theory, and some of the proofs seem very difficult to come up with
– eatfood
Jul 19 at 3:20
1
1
math.stackexchange.com/questions/1351994/…
– individ
Jul 18 at 17:00
math.stackexchange.com/questions/1351994/…
– individ
Jul 18 at 17:00
2
2
Have you ever seen the "Gaussian" proofs that if $a^2+b^2=c$ and $a, b, c$ are relatively prime, then all prime factors of $c$ are of the form $4k+1$? This operates on very similar principles using a different ring of integers.
– Steven Stadnicki
Jul 18 at 17:00
Have you ever seen the "Gaussian" proofs that if $a^2+b^2=c$ and $a, b, c$ are relatively prime, then all prime factors of $c$ are of the form $4k+1$? This operates on very similar principles using a different ring of integers.
– Steven Stadnicki
Jul 18 at 17:00
@individ thanks for the link! ill check it out
– eatfood
Jul 19 at 3:19
@individ thanks for the link! ill check it out
– eatfood
Jul 19 at 3:19
@StevenStadnicki no I haven't, I have only just started on learning number theory, and some of the proofs seem very difficult to come up with
– eatfood
Jul 19 at 3:20
@StevenStadnicki no I haven't, I have only just started on learning number theory, and some of the proofs seem very difficult to come up with
– eatfood
Jul 19 at 3:20
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
1
down vote
accepted
Here is a proof based on quadratic reciprocity.
Suppose $p=3k-1|a^2-ab+b^2$ with $a,b$ relatively prime. Neither $a$ nor $b$ can have zero residue $bmod p$, else they both would which the hypothesis denies. Thus there exists a nonzero residue $requiv ab^-1bmod p$ such that $r^2-r+1equiv 0$. Multiplying by $4$ and completing the square gives $(2r-1)^2equiv -3$. Therefore the Legendre symbol $(-3|p)=+1$ if $p$ is as assumed above.
But $(p|3)=(3k-1|3)=-1$ and $-3equiv +1bmod 4$, so QR forces the contradictory conclusion $(-3|p)=-1$.
The case $p=3$ remains and this is a bit tricky. There are multiples of $3$ having the form $a^2-ab+b^2$ where $a$ and $b$ are relatively prime. We just need $aequiv -bbmod 3$ because $a^2-ab+b^2equiv (a+b)^2bmod 3$. But, if $aequiv -bbmod 3$ with the common residue being $1$ or $2$, we find that $c^2equiv 3bmod 9$ which doesn't work.
answered Jul 18 at 17:25
Oscar Lanzi
9,98911632
1
Hi Oscar, this is a really neat way to solve it. I got to $r^2 - r + 1 equiv 0 pmod p$ but I did not know how to proceed further. Completing the square to introduce the Legendre symbol with 3 as the other prime is really neat. Thanks alot!
– eatfood
Jul 19 at 3:15
So more generally, for $p ne 2$ prime (and $a notequiv 0 pmodp$), $ar^2 + br + c equiv 0 pmodp$ has solutions if and only if $(b^2-4ac | p) = 1$. (Slightly different proof to the completing squares one: if the two roots are $r_1,r_2$ then $b^2-4ac = [a (r_1 - r_2)]^2$.)
– Daniel Schepler
Jul 19 at 15:32
One degenerate solution if $(b^2-4ac|p)=0$, e.g. $x^2-x-1equiv 0bmod 5$ where $b^2-4ac=5equiv 0$ has a solution $xequiv 3$. The existence of such a solution in the case of this problem is why we had to treat $p=3$ separately.
– Oscar Lanzi
Jul 19 at 21:20
add a comment |Â
up vote
3
down vote
Suppose $p mid c$, so that $a^2 - ab + b^2 equiv 0 pmodp$. That implies that $a^3 + b^3 equiv 0 pmodp$. By the assumption that $a$ and $b$ are each relatively prime to $c$, we have that $p nmid a, b$, so $-a b^-1$ has cube equal to 1 in $mathbbZ / p mathbbZ$. Also, if it were the case that $a equiv -b pmodp$, then we would have $3 a^2 equiv a^2 - ab + b^2 equiv 0 pmodp$, giving a contradiction (as long as $pne 3$; but in this case, for example if $a = 3m+1$ and $b=3n-1$, then $a^2 - ab + b^2 = 9m^2 - 9mn + 9n^2 -9m + 9n + 3 equiv 3 pmod9$ contradicting the fact that $3 mid c^2$ implies $9 mid c^2$). Therefore, $-a b^-1$ has order exactly three in the group of units of $mathbbZ / p mathbbZ$, implying that 3 divides $|(mathbbZ / p mathbbZ)^*| = p-1$.
answered Jul 18 at 17:15
Daniel Schepler
6,9131514
1
Hi Daniel, that is a really natural way to solve it. I did not even think of $a^3 + b^3 equiv 0 pmod p$. Although i really like this solution, I accepted the Oscar's answer because the problem is located in the QR section of the handout so I'm assuming his solution is the one intended by the author. Thanks very much still!
– eatfood
Jul 19 at 3:12
add a comment |Â
up vote
0
down vote
Here is an algebraic theoretical proof parallel to the "gaussian" proof of Fermat's theorem on sums of squares. You may find it too complicated, but actually the general trend in math is to try to embed particular questions into larger and larger general theories in order to solve in one stroke whole families of problems which are of the same nature (*)
First replace the Gauss ring $mathbf Z[i]$ by the Eisenstein ring $E=mathbf Z[j]$, which is the ring of integers of the quadratic field $mathbf Q(j)$, where $j$ is a primitive 3rd root of unity. It is classically known that $E$ is a principal ideal ring, so the theory of division in $E$ for ideals and for elements is the same up to the units of $E$, which are plainly the powers of $pm j$. The prime elements (ideals) of $E$ are deduced from those of $mathbf Z$ in the following manner : a prime $p$ of $mathbf Z$ does not necessarily remain prime in $E$, but it can decompose only in 3 possible ways : (1) $p$ is inert, i.e. remains prime, iff $pequiv 2$ mod $3$ ; (2) $p$ splits, i.e. $p=pibarpi$ (where $pi$ is a prime of $E$) iff $pequiv 1$ mod $3$ ; (3) $p$ ramifies in $E$, i.e. $p=pi^2$ iff $p=3$ (see any textbook in ANT).
Now the equation $a^2-ab+b^2=c^2$ in $mathbf Z$ reads $(a+bj)(a+bj^2)=c^2$ in $E$, where the UFD property implies that the prime divisors $pi$ of $c$ are exactly such that $pi$ divides $a+bj$, say, and the conjugate $bar pi$ divides $a+bj^2$. By uniqueness again, $pibar pi$ will divide $c$, i.e. the rational primes $p$ which divide $c$ must split.
(*) An archetypical example lies in the attempts to solve FLT by the same approach as above. Actually Kummer showed FLT along these lines - but of course with more involved arguments - in the so called regular case, i.e. when the ring $mathbf Z[zeta_p]$ (where $zeta_p$ is a primitive $p$-th root of unity) is principal.
answered Jul 20 at 14:18
nguyen quang do
7,4521621
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Here is a proof based on quadratic reciprocity.
Suppose $p=3k-1|a^2-ab+b^2$ with $a,b$ relatively prime. Neither $a$ nor $b$ can have zero residue $bmod p$, else they both would which the hypothesis denies. Thus there exists a nonzero residue $requiv ab^-1bmod p$ such that $r^2-r+1equiv 0$. Multiplying by $4$ and completing the square gives $(2r-1)^2equiv -3$. Therefore the Legendre symbol $(-3|p)=+1$ if $p$ is as assumed above.
But $(p|3)=(3k-1|3)=-1$ and $-3equiv +1bmod 4$, so QR forces the contradictory conclusion $(-3|p)=-1$.
The case $p=3$ remains and this is a bit tricky. There are multiples of $3$ having the form $a^2-ab+b^2$ where $a$ and $b$ are relatively prime. We just need $aequiv -bbmod 3$ because $a^2-ab+b^2equiv (a+b)^2bmod 3$. But, if $aequiv -bbmod 3$ with the common residue being $1$ or $2$, we find that $c^2equiv 3bmod 9$ which doesn't work.
answered Jul 18 at 17:25
Oscar Lanzi
9,98911632
1
Hi Oscar, this is a really neat way to solve it. I got to $r^2 - r + 1 equiv 0 pmod p$ but I did not know how to proceed further. Completing the square to introduce the Legendre symbol with 3 as the other prime is really neat. Thanks alot!
– eatfood
Jul 19 at 3:15
So more generally, for $p ne 2$ prime (and $a notequiv 0 pmodp$), $ar^2 + br + c equiv 0 pmodp$ has solutions if and only if $(b^2-4ac | p) = 1$. (Slightly different proof to the completing squares one: if the two roots are $r_1,r_2$ then $b^2-4ac = [a (r_1 - r_2)]^2$.)
– Daniel Schepler
Jul 19 at 15:32
One degenerate solution if $(b^2-4ac|p)=0$, e.g. $x^2-x-1equiv 0bmod 5$ where $b^2-4ac=5equiv 0$ has a solution $xequiv 3$. The existence of such a solution in the case of this problem is why we had to treat $p=3$ separately.
– Oscar Lanzi
Jul 19 at 21:20
add a comment |Â
up vote
1
down vote
accepted
Here is a proof based on quadratic reciprocity.
Suppose $p=3k-1|a^2-ab+b^2$ with $a,b$ relatively prime. Neither $a$ nor $b$ can have zero residue $bmod p$, else they both would which the hypothesis denies. Thus there exists a nonzero residue $requiv ab^-1bmod p$ such that $r^2-r+1equiv 0$. Multiplying by $4$ and completing the square gives $(2r-1)^2equiv -3$. Therefore the Legendre symbol $(-3|p)=+1$ if $p$ is as assumed above.
But $(p|3)=(3k-1|3)=-1$ and $-3equiv +1bmod 4$, so QR forces the contradictory conclusion $(-3|p)=-1$.
The case $p=3$ remains and this is a bit tricky. There are multiples of $3$ having the form $a^2-ab+b^2$ where $a$ and $b$ are relatively prime. We just need $aequiv -bbmod 3$ because $a^2-ab+b^2equiv (a+b)^2bmod 3$. But, if $aequiv -bbmod 3$ with the common residue being $1$ or $2$, we find that $c^2equiv 3bmod 9$ which doesn't work.
answered Jul 18 at 17:25
Oscar Lanzi
9,98911632
1
Hi Oscar, this is a really neat way to solve it. I got to $r^2 - r + 1 equiv 0 pmod p$ but I did not know how to proceed further. Completing the square to introduce the Legendre symbol with 3 as the other prime is really neat. Thanks alot!
– eatfood
Jul 19 at 3:15
So more generally, for $p ne 2$ prime (and $a notequiv 0 pmodp$), $ar^2 + br + c equiv 0 pmodp$ has solutions if and only if $(b^2-4ac | p) = 1$. (Slightly different proof to the completing squares one: if the two roots are $r_1,r_2$ then $b^2-4ac = [a (r_1 - r_2)]^2$.)
– Daniel Schepler
Jul 19 at 15:32
One degenerate solution if $(b^2-4ac|p)=0$, e.g. $x^2-x-1equiv 0bmod 5$ where $b^2-4ac=5equiv 0$ has a solution $xequiv 3$. The existence of such a solution in the case of this problem is why we had to treat $p=3$ separately.
– Oscar Lanzi
Jul 19 at 21:20
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Here is a proof based on quadratic reciprocity.
Suppose $p=3k-1|a^2-ab+b^2$ with $a,b$ relatively prime. Neither $a$ nor $b$ can have zero residue $bmod p$, else they both would which the hypothesis denies. Thus there exists a nonzero residue $requiv ab^-1bmod p$ such that $r^2-r+1equiv 0$. Multiplying by $4$ and completing the square gives $(2r-1)^2equiv -3$. Therefore the Legendre symbol $(-3|p)=+1$ if $p$ is as assumed above.
But $(p|3)=(3k-1|3)=-1$ and $-3equiv +1bmod 4$, so QR forces the contradictory conclusion $(-3|p)=-1$.
The case $p=3$ remains and this is a bit tricky. There are multiples of $3$ having the form $a^2-ab+b^2$ where $a$ and $b$ are relatively prime. We just need $aequiv -bbmod 3$ because $a^2-ab+b^2equiv (a+b)^2bmod 3$. But, if $aequiv -bbmod 3$ with the common residue being $1$ or $2$, we find that $c^2equiv 3bmod 9$ which doesn't work.
answered Jul 18 at 17:25
Oscar Lanzi
9,98911632
Here is a proof based on quadratic reciprocity.
Suppose $p=3k-1|a^2-ab+b^2$ with $a,b$ relatively prime. Neither $a$ nor $b$ can have zero residue $bmod p$, else they both would which the hypothesis denies. Thus there exists a nonzero residue $requiv ab^-1bmod p$ such that $r^2-r+1equiv 0$. Multiplying by $4$ and completing the square gives $(2r-1)^2equiv -3$. Therefore the Legendre symbol $(-3|p)=+1$ if $p$ is as assumed above.
But $(p|3)=(3k-1|3)=-1$ and $-3equiv +1bmod 4$, so QR forces the contradictory conclusion $(-3|p)=-1$.
The case $p=3$ remains and this is a bit tricky. There are multiples of $3$ having the form $a^2-ab+b^2$ where $a$ and $b$ are relatively prime. We just need $aequiv -bbmod 3$ because $a^2-ab+b^2equiv (a+b)^2bmod 3$. But, if $aequiv -bbmod 3$ with the common residue being $1$ or $2$, we find that $c^2equiv 3bmod 9$ which doesn't work.
answered Jul 18 at 17:25
Oscar Lanzi
9,98911632
edited Jul 23 at 1:43
answered Jul 18 at 17:25
Oscar Lanzi
9,98911632
answered Jul 18 at 17:25
Oscar Lanzi
9,98911632
answered Jul 18 at 17:25
Oscar Lanzi
9,98911632
9,98911632
1
Hi Oscar, this is a really neat way to solve it. I got to $r^2 - r + 1 equiv 0 pmod p$ but I did not know how to proceed further. Completing the square to introduce the Legendre symbol with 3 as the other prime is really neat. Thanks alot!
– eatfood
Jul 19 at 3:15
So more generally, for $p ne 2$ prime (and $a notequiv 0 pmodp$), $ar^2 + br + c equiv 0 pmodp$ has solutions if and only if $(b^2-4ac | p) = 1$. (Slightly different proof to the completing squares one: if the two roots are $r_1,r_2$ then $b^2-4ac = [a (r_1 - r_2)]^2$.)
– Daniel Schepler
Jul 19 at 15:32
One degenerate solution if $(b^2-4ac|p)=0$, e.g. $x^2-x-1equiv 0bmod 5$ where $b^2-4ac=5equiv 0$ has a solution $xequiv 3$. The existence of such a solution in the case of this problem is why we had to treat $p=3$ separately.
– Oscar Lanzi
Jul 19 at 21:20
add a comment |Â
1
Hi Oscar, this is a really neat way to solve it. I got to $r^2 - r + 1 equiv 0 pmod p$ but I did not know how to proceed further. Completing the square to introduce the Legendre symbol with 3 as the other prime is really neat. Thanks alot!
– eatfood
Jul 19 at 3:15
So more generally, for $p ne 2$ prime (and $a notequiv 0 pmodp$), $ar^2 + br + c equiv 0 pmodp$ has solutions if and only if $(b^2-4ac | p) = 1$. (Slightly different proof to the completing squares one: if the two roots are $r_1,r_2$ then $b^2-4ac = [a (r_1 - r_2)]^2$.)
– Daniel Schepler
Jul 19 at 15:32
One degenerate solution if $(b^2-4ac|p)=0$, e.g. $x^2-x-1equiv 0bmod 5$ where $b^2-4ac=5equiv 0$ has a solution $xequiv 3$. The existence of such a solution in the case of this problem is why we had to treat $p=3$ separately.
– Oscar Lanzi
Jul 19 at 21:20
1
1
Hi Oscar, this is a really neat way to solve it. I got to $r^2 - r + 1 equiv 0 pmod p$ but I did not know how to proceed further. Completing the square to introduce the Legendre symbol with 3 as the other prime is really neat. Thanks alot!
– eatfood
Jul 19 at 3:15
Hi Oscar, this is a really neat way to solve it. I got to $r^2 - r + 1 equiv 0 pmod p$ but I did not know how to proceed further. Completing the square to introduce the Legendre symbol with 3 as the other prime is really neat. Thanks alot!
– eatfood
Jul 19 at 3:15
So more generally, for $p ne 2$ prime (and $a notequiv 0 pmodp$), $ar^2 + br + c equiv 0 pmodp$ has solutions if and only if $(b^2-4ac | p) = 1$. (Slightly different proof to the completing squares one: if the two roots are $r_1,r_2$ then $b^2-4ac = [a (r_1 - r_2)]^2$.)
– Daniel Schepler
Jul 19 at 15:32
So more generally, for $p ne 2$ prime (and $a notequiv 0 pmodp$), $ar^2 + br + c equiv 0 pmodp$ has solutions if and only if $(b^2-4ac | p) = 1$. (Slightly different proof to the completing squares one: if the two roots are $r_1,r_2$ then $b^2-4ac = [a (r_1 - r_2)]^2$.)
– Daniel Schepler
Jul 19 at 15:32
One degenerate solution if $(b^2-4ac|p)=0$, e.g. $x^2-x-1equiv 0bmod 5$ where $b^2-4ac=5equiv 0$ has a solution $xequiv 3$. The existence of such a solution in the case of this problem is why we had to treat $p=3$ separately.
– Oscar Lanzi
Jul 19 at 21:20
One degenerate solution if $(b^2-4ac|p)=0$, e.g. $x^2-x-1equiv 0bmod 5$ where $b^2-4ac=5equiv 0$ has a solution $xequiv 3$. The existence of such a solution in the case of this problem is why we had to treat $p=3$ separately.
– Oscar Lanzi
Jul 19 at 21:20
add a comment |Â
up vote
3
down vote
Suppose $p mid c$, so that $a^2 - ab + b^2 equiv 0 pmodp$. That implies that $a^3 + b^3 equiv 0 pmodp$. By the assumption that $a$ and $b$ are each relatively prime to $c$, we have that $p nmid a, b$, so $-a b^-1$ has cube equal to 1 in $mathbbZ / p mathbbZ$. Also, if it were the case that $a equiv -b pmodp$, then we would have $3 a^2 equiv a^2 - ab + b^2 equiv 0 pmodp$, giving a contradiction (as long as $pne 3$; but in this case, for example if $a = 3m+1$ and $b=3n-1$, then $a^2 - ab + b^2 = 9m^2 - 9mn + 9n^2 -9m + 9n + 3 equiv 3 pmod9$ contradicting the fact that $3 mid c^2$ implies $9 mid c^2$). Therefore, $-a b^-1$ has order exactly three in the group of units of $mathbbZ / p mathbbZ$, implying that 3 divides $|(mathbbZ / p mathbbZ)^*| = p-1$.
answered Jul 18 at 17:15
Daniel Schepler
6,9131514
1
Hi Daniel, that is a really natural way to solve it. I did not even think of $a^3 + b^3 equiv 0 pmod p$. Although i really like this solution, I accepted the Oscar's answer because the problem is located in the QR section of the handout so I'm assuming his solution is the one intended by the author. Thanks very much still!
– eatfood
Jul 19 at 3:12
add a comment |Â
up vote
3
down vote
Suppose $p mid c$, so that $a^2 - ab + b^2 equiv 0 pmodp$. That implies that $a^3 + b^3 equiv 0 pmodp$. By the assumption that $a$ and $b$ are each relatively prime to $c$, we have that $p nmid a, b$, so $-a b^-1$ has cube equal to 1 in $mathbbZ / p mathbbZ$. Also, if it were the case that $a equiv -b pmodp$, then we would have $3 a^2 equiv a^2 - ab + b^2 equiv 0 pmodp$, giving a contradiction (as long as $pne 3$; but in this case, for example if $a = 3m+1$ and $b=3n-1$, then $a^2 - ab + b^2 = 9m^2 - 9mn + 9n^2 -9m + 9n + 3 equiv 3 pmod9$ contradicting the fact that $3 mid c^2$ implies $9 mid c^2$). Therefore, $-a b^-1$ has order exactly three in the group of units of $mathbbZ / p mathbbZ$, implying that 3 divides $|(mathbbZ / p mathbbZ)^*| = p-1$.
answered Jul 18 at 17:15
Daniel Schepler
6,9131514
1
Hi Daniel, that is a really natural way to solve it. I did not even think of $a^3 + b^3 equiv 0 pmod p$. Although i really like this solution, I accepted the Oscar's answer because the problem is located in the QR section of the handout so I'm assuming his solution is the one intended by the author. Thanks very much still!
– eatfood
Jul 19 at 3:12
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Suppose $p mid c$, so that $a^2 - ab + b^2 equiv 0 pmodp$. That implies that $a^3 + b^3 equiv 0 pmodp$. By the assumption that $a$ and $b$ are each relatively prime to $c$, we have that $p nmid a, b$, so $-a b^-1$ has cube equal to 1 in $mathbbZ / p mathbbZ$. Also, if it were the case that $a equiv -b pmodp$, then we would have $3 a^2 equiv a^2 - ab + b^2 equiv 0 pmodp$, giving a contradiction (as long as $pne 3$; but in this case, for example if $a = 3m+1$ and $b=3n-1$, then $a^2 - ab + b^2 = 9m^2 - 9mn + 9n^2 -9m + 9n + 3 equiv 3 pmod9$ contradicting the fact that $3 mid c^2$ implies $9 mid c^2$). Therefore, $-a b^-1$ has order exactly three in the group of units of $mathbbZ / p mathbbZ$, implying that 3 divides $|(mathbbZ / p mathbbZ)^*| = p-1$.
answered Jul 18 at 17:15
Daniel Schepler
6,9131514
Suppose $p mid c$, so that $a^2 - ab + b^2 equiv 0 pmodp$. That implies that $a^3 + b^3 equiv 0 pmodp$. By the assumption that $a$ and $b$ are each relatively prime to $c$, we have that $p nmid a, b$, so $-a b^-1$ has cube equal to 1 in $mathbbZ / p mathbbZ$. Also, if it were the case that $a equiv -b pmodp$, then we would have $3 a^2 equiv a^2 - ab + b^2 equiv 0 pmodp$, giving a contradiction (as long as $pne 3$; but in this case, for example if $a = 3m+1$ and $b=3n-1$, then $a^2 - ab + b^2 = 9m^2 - 9mn + 9n^2 -9m + 9n + 3 equiv 3 pmod9$ contradicting the fact that $3 mid c^2$ implies $9 mid c^2$). Therefore, $-a b^-1$ has order exactly three in the group of units of $mathbbZ / p mathbbZ$, implying that 3 divides $|(mathbbZ / p mathbbZ)^*| = p-1$.
answered Jul 18 at 17:15
Daniel Schepler
6,9131514
edited Jul 18 at 17:50
answered Jul 18 at 17:15
Daniel Schepler
6,9131514
answered Jul 18 at 17:15
Daniel Schepler
6,9131514
answered Jul 18 at 17:15
Daniel Schepler
6,9131514
6,9131514
1
Hi Daniel, that is a really natural way to solve it. I did not even think of $a^3 + b^3 equiv 0 pmod p$. Although i really like this solution, I accepted the Oscar's answer because the problem is located in the QR section of the handout so I'm assuming his solution is the one intended by the author. Thanks very much still!
– eatfood
Jul 19 at 3:12
add a comment |Â
1
Hi Daniel, that is a really natural way to solve it. I did not even think of $a^3 + b^3 equiv 0 pmod p$. Although i really like this solution, I accepted the Oscar's answer because the problem is located in the QR section of the handout so I'm assuming his solution is the one intended by the author. Thanks very much still!
– eatfood
Jul 19 at 3:12
1
1
Hi Daniel, that is a really natural way to solve it. I did not even think of $a^3 + b^3 equiv 0 pmod p$. Although i really like this solution, I accepted the Oscar's answer because the problem is located in the QR section of the handout so I'm assuming his solution is the one intended by the author. Thanks very much still!
– eatfood
Jul 19 at 3:12
Hi Daniel, that is a really natural way to solve it. I did not even think of $a^3 + b^3 equiv 0 pmod p$. Although i really like this solution, I accepted the Oscar's answer because the problem is located in the QR section of the handout so I'm assuming his solution is the one intended by the author. Thanks very much still!
– eatfood
Jul 19 at 3:12
add a comment |Â
up vote
0
down vote
Here is an algebraic theoretical proof parallel to the "gaussian" proof of Fermat's theorem on sums of squares. You may find it too complicated, but actually the general trend in math is to try to embed particular questions into larger and larger general theories in order to solve in one stroke whole families of problems which are of the same nature (*)
First replace the Gauss ring $mathbf Z[i]$ by the Eisenstein ring $E=mathbf Z[j]$, which is the ring of integers of the quadratic field $mathbf Q(j)$, where $j$ is a primitive 3rd root of unity. It is classically known that $E$ is a principal ideal ring, so the theory of division in $E$ for ideals and for elements is the same up to the units of $E$, which are plainly the powers of $pm j$. The prime elements (ideals) of $E$ are deduced from those of $mathbf Z$ in the following manner : a prime $p$ of $mathbf Z$ does not necessarily remain prime in $E$, but it can decompose only in 3 possible ways : (1) $p$ is inert, i.e. remains prime, iff $pequiv 2$ mod $3$ ; (2) $p$ splits, i.e. $p=pibarpi$ (where $pi$ is a prime of $E$) iff $pequiv 1$ mod $3$ ; (3) $p$ ramifies in $E$, i.e. $p=pi^2$ iff $p=3$ (see any textbook in ANT).
Now the equation $a^2-ab+b^2=c^2$ in $mathbf Z$ reads $(a+bj)(a+bj^2)=c^2$ in $E$, where the UFD property implies that the prime divisors $pi$ of $c$ are exactly such that $pi$ divides $a+bj$, say, and the conjugate $bar pi$ divides $a+bj^2$. By uniqueness again, $pibar pi$ will divide $c$, i.e. the rational primes $p$ which divide $c$ must split.
(*) An archetypical example lies in the attempts to solve FLT by the same approach as above. Actually Kummer showed FLT along these lines - but of course with more involved arguments - in the so called regular case, i.e. when the ring $mathbf Z[zeta_p]$ (where $zeta_p$ is a primitive $p$-th root of unity) is principal.
answered Jul 20 at 14:18
nguyen quang do
7,4521621
add a comment |Â
up vote
0
down vote
Here is an algebraic theoretical proof parallel to the "gaussian" proof of Fermat's theorem on sums of squares. You may find it too complicated, but actually the general trend in math is to try to embed particular questions into larger and larger general theories in order to solve in one stroke whole families of problems which are of the same nature (*)
First replace the Gauss ring $mathbf Z[i]$ by the Eisenstein ring $E=mathbf Z[j]$, which is the ring of integers of the quadratic field $mathbf Q(j)$, where $j$ is a primitive 3rd root of unity. It is classically known that $E$ is a principal ideal ring, so the theory of division in $E$ for ideals and for elements is the same up to the units of $E$, which are plainly the powers of $pm j$. The prime elements (ideals) of $E$ are deduced from those of $mathbf Z$ in the following manner : a prime $p$ of $mathbf Z$ does not necessarily remain prime in $E$, but it can decompose only in 3 possible ways : (1) $p$ is inert, i.e. remains prime, iff $pequiv 2$ mod $3$ ; (2) $p$ splits, i.e. $p=pibarpi$ (where $pi$ is a prime of $E$) iff $pequiv 1$ mod $3$ ; (3) $p$ ramifies in $E$, i.e. $p=pi^2$ iff $p=3$ (see any textbook in ANT).
Now the equation $a^2-ab+b^2=c^2$ in $mathbf Z$ reads $(a+bj)(a+bj^2)=c^2$ in $E$, where the UFD property implies that the prime divisors $pi$ of $c$ are exactly such that $pi$ divides $a+bj$, say, and the conjugate $bar pi$ divides $a+bj^2$. By uniqueness again, $pibar pi$ will divide $c$, i.e. the rational primes $p$ which divide $c$ must split.
(*) An archetypical example lies in the attempts to solve FLT by the same approach as above. Actually Kummer showed FLT along these lines - but of course with more involved arguments - in the so called regular case, i.e. when the ring $mathbf Z[zeta_p]$ (where $zeta_p$ is a primitive $p$-th root of unity) is principal.
answered Jul 20 at 14:18
nguyen quang do
7,4521621
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Here is an algebraic theoretical proof parallel to the "gaussian" proof of Fermat's theorem on sums of squares. You may find it too complicated, but actually the general trend in math is to try to embed particular questions into larger and larger general theories in order to solve in one stroke whole families of problems which are of the same nature (*)
First replace the Gauss ring $mathbf Z[i]$ by the Eisenstein ring $E=mathbf Z[j]$, which is the ring of integers of the quadratic field $mathbf Q(j)$, where $j$ is a primitive 3rd root of unity. It is classically known that $E$ is a principal ideal ring, so the theory of division in $E$ for ideals and for elements is the same up to the units of $E$, which are plainly the powers of $pm j$. The prime elements (ideals) of $E$ are deduced from those of $mathbf Z$ in the following manner : a prime $p$ of $mathbf Z$ does not necessarily remain prime in $E$, but it can decompose only in 3 possible ways : (1) $p$ is inert, i.e. remains prime, iff $pequiv 2$ mod $3$ ; (2) $p$ splits, i.e. $p=pibarpi$ (where $pi$ is a prime of $E$) iff $pequiv 1$ mod $3$ ; (3) $p$ ramifies in $E$, i.e. $p=pi^2$ iff $p=3$ (see any textbook in ANT).
Now the equation $a^2-ab+b^2=c^2$ in $mathbf Z$ reads $(a+bj)(a+bj^2)=c^2$ in $E$, where the UFD property implies that the prime divisors $pi$ of $c$ are exactly such that $pi$ divides $a+bj$, say, and the conjugate $bar pi$ divides $a+bj^2$. By uniqueness again, $pibar pi$ will divide $c$, i.e. the rational primes $p$ which divide $c$ must split.
(*) An archetypical example lies in the attempts to solve FLT by the same approach as above. Actually Kummer showed FLT along these lines - but of course with more involved arguments - in the so called regular case, i.e. when the ring $mathbf Z[zeta_p]$ (where $zeta_p$ is a primitive $p$-th root of unity) is principal.
answered Jul 20 at 14:18
nguyen quang do
7,4521621
Here is an algebraic theoretical proof parallel to the "gaussian" proof of Fermat's theorem on sums of squares. You may find it too complicated, but actually the general trend in math is to try to embed particular questions into larger and larger general theories in order to solve in one stroke whole families of problems which are of the same nature (*)
First replace the Gauss ring $mathbf Z[i]$ by the Eisenstein ring $E=mathbf Z[j]$, which is the ring of integers of the quadratic field $mathbf Q(j)$, where $j$ is a primitive 3rd root of unity. It is classically known that $E$ is a principal ideal ring, so the theory of division in $E$ for ideals and for elements is the same up to the units of $E$, which are plainly the powers of $pm j$. The prime elements (ideals) of $E$ are deduced from those of $mathbf Z$ in the following manner : a prime $p$ of $mathbf Z$ does not necessarily remain prime in $E$, but it can decompose only in 3 possible ways : (1) $p$ is inert, i.e. remains prime, iff $pequiv 2$ mod $3$ ; (2) $p$ splits, i.e. $p=pibarpi$ (where $pi$ is a prime of $E$) iff $pequiv 1$ mod $3$ ; (3) $p$ ramifies in $E$, i.e. $p=pi^2$ iff $p=3$ (see any textbook in ANT).
Now the equation $a^2-ab+b^2=c^2$ in $mathbf Z$ reads $(a+bj)(a+bj^2)=c^2$ in $E$, where the UFD property implies that the prime divisors $pi$ of $c$ are exactly such that $pi$ divides $a+bj$, say, and the conjugate $bar pi$ divides $a+bj^2$. By uniqueness again, $pibar pi$ will divide $c$, i.e. the rational primes $p$ which divide $c$ must split.
(*) An archetypical example lies in the attempts to solve FLT by the same approach as above. Actually Kummer showed FLT along these lines - but of course with more involved arguments - in the so called regular case, i.e. when the ring $mathbf Z[zeta_p]$ (where $zeta_p$ is a primitive $p$-th root of unity) is principal.
answered Jul 20 at 14:18
nguyen quang do
7,4521621
answered Jul 20 at 14:18
nguyen quang do
7,4521621
answered Jul 20 at 14:18
nguyen quang do
7,4521621
answered Jul 20 at 14:18
nguyen quang do
7,4521621
7,4521621
add a comment |Â
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%2f2855769%2fa2%25e2%2588%2592abb2-c2-show-prime-factors-of-c-are-of-the-form-6k-1%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
1
math.stackexchange.com/questions/1351994/…
– individ
Jul 18 at 17:00
2
Have you ever seen the "Gaussian" proofs that if $a^2+b^2=c$ and $a, b, c$ are relatively prime, then all prime factors of $c$ are of the form $4k+1$? This operates on very similar principles using a different ring of integers.
– Steven Stadnicki
Jul 18 at 17:00
@individ thanks for the link! ill check it out
– eatfood
Jul 19 at 3:19
@StevenStadnicki no I haven't, I have only just started on learning number theory, and some of the proofs seem very difficult to come up with
– eatfood
Jul 19 at 3:20