# A number is prime if and only if …

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?

• what is a gcd of fractions??????????????????? – Will Jagy May 7 '16 at 0:48
• 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. – Oliver G May 7 '16 at 0:53
• 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. – 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$.