Prove that a number $p$ is prime if and only if the $\gcd(\text{numerator},\text{denominator})$ of all fractions of the form $$\frac{1}{p - 1}, \frac{2}{p - 2}, \frac{3}{p - 3}, \ldots, \frac{k}{p - k}, \ldots, \frac{(p - 1)/2}{ (p - 1) / 2 + 1}$$ equals $1$.
The proof in the forwards direction by contradiction is simple because it leads to $\gcd(\text{fraction}) \neq 1$. In the reverse direction I have (by contrapositive): $p$ is composite (odd or even) implies there exists a fraction whose $\gcd$ is not $1$. It's true for even composites because any even $k$ gives a $\gcd$ not equal to $1$, but for an odd composite I'm having trouble seeing how to prove it.
Anyone have any ideas about the reverse direction?
Answer
Suppose that $p\gt 4$ is not prime. Then there exist positive integers $a$ and $b$, with $1\lt a\le b\lt p$ such that $ab=p$. In particular, we have $a\le \frac{p-1}{2}$. To show this, we only need to show that $ab-1\ge 2a$, or equivalently that $a(b-2)\ge 1$. This is clear, since $b\gt 2$.
Finally, observe that $\gcd(a,p-a)=\gcd(a,ab-a)=a\ne 1$.
Remark: If $p$ is even, then $\frac{p-1}{2}$ is not an integer. So it seems likely that we are to assume that $p$ is odd. However, the argument goes through for even $p\gt 4$, using the fractions with numerator up to $\left\lfloor\frac{p-1}{2}\right\rfloor$. Note that if we interpret the product as being up to $\left\lfloor\frac{p-1}{2}\right\rfloor$, then the result is not correct for the composite number $p=4$.
No comments:
Post a Comment