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?

  • 5
    $\begingroup$ what is a gcd of fractions??????????????????? $\endgroup$ – Will Jagy May 7 '16 at 0:48
  • 1
    $\begingroup$ gcd (numerator,denominator) is what I'm trying to say. That you cannot factor out the same positive integer from the numerator and the denominator. $\endgroup$ – Oliver G May 7 '16 at 0:53
  • 1
    $\begingroup$ If p =mk then m/(p-m) is not in lowest terms and gcd (m,p-m) ge m. Not sure why you think p being even makes any difference. $\endgroup$ – fleablood May 7 '16 at 2:49

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.