24
$\begingroup$

Can you prove or disprove the following claim:

Let $n$ be a natural number greater than two , then $$n \text{ is prime iff } \binom{n^2}{n} \equiv n \pmod{n^4}$$

You can run this test here. I have verified this claim for all $n$ up to $100000$ .

$\endgroup$
4
  • $\begingroup$ For what it's worth, $n^2+1 \text{ is prime iff } \binom{n^2}{n} \equiv 1 \pmod{n^2+1}$. $\endgroup$
    – Trevor
    Commented Aug 7, 2020 at 1:37
  • 1
    $\begingroup$ LaTeX-only titles are discouraged because they prevent others from having the normal right-click menu available to them. $\endgroup$
    – anon
    Commented Aug 7, 2020 at 1:39
  • 1
    $\begingroup$ Verified up to 260000: all primes without gaps. $\endgroup$ Commented Aug 7, 2020 at 3:05
  • $\begingroup$ This may be particular case of Wilson's theorem. en.wikipedia.org/wiki/Wilson%27s_theorem $\endgroup$ Commented Aug 8, 2020 at 10:42

3 Answers 3

22
+150
$\begingroup$

Unfortunately, it appears that the claim is false. My counterexample is $n=16843^2$. Note that $16843$ is a Wolstenholme prime. Henceforth set $p=16843$ (so that our counterexample is $n=p^2$).

Here is the "proof" of my counterexample, which seems to be too large to compute directly (crashed the Sage program and Wolfram didn't understand it directly, so more work was needed).

Note that it suffices to show $$\binom{p^4}{p^2}\equiv p^2\pmod{p^8}.$$ By CAMO 2020/2, since $p=16843>3$, then we have $$\binom{p^4}{p^2}\equiv \binom{p^3}p\pmod{p^9}$$ which is of course strong enough to tell us that $$\binom{p^4}{p^2}\equiv \binom{p^3}p\pmod{p^8}.$$

Now, Wolfram Alpha computes $$\binom{p^3}{p}-p^2\equiv 0\pmod{p^8},$$ which implies $$\binom{p^4}{p^2}\equiv p^2\pmod{p^8},$$ which proves that the counterexample $n=p^2$ works.

Note: With enough work, I think that it's possible to show without using computer aid that $n=p^2$ is a counterexample iff $p$ is a Wolstenholme prime.

EDIT: I have figured out a proof that all $n=p^2$ for $p$ a Wolstenholme prime are counterexamples. Follow the solution posted by TheUltimate123 here, and modify the falling factorial congruence lemma to hold modulo $p^{k+3}$. The proof works the exact same except for two changes: First, we prove the lemma only for $i=0$, as the $n$ in the problem is equal to 1 (as in $\binom{p^3}{p\cdot 1}$). Also, we use the fact that $p$ is a Wolstenholme prime to note $$\sum_{j=1}^{p-1} \frac1j\equiv 0\pmod{p^3},$$ so that the lemma may hold modulo $p^{k+3}$.

This gives us the following lemma: for Wolstenholme primes $p$, $$\binom{p^k}{p}\equiv p^{k-1}\pmod{p^{2k+2}}.$$

Now, to finish, note $$\binom{p^4}{p^2}\equiv\binom{p^3}p\pmod{p^{2\cdot 4+1}}$$ and $$\binom{p^3}{p}\equiv p^2\pmod{p^{2\cdot 3+2}}$$ which combined implies that for all Wolstenholme primes $p$, $$\binom{p^4}{p^2}\equiv p^2\pmod{p^8}.$$

Interesting Aside (delete if off-topic): CAMO 2020/2 tells us that all primes $p>3$ satisfy $$\binom{p^2}p\equiv p\pmod{p^5},$$ so perhaps a better question to ask would be: Is it true that for all natural numbers $n>3$, $$\binom{n^2}n\equiv n\pmod{n^5}\iff n\in\mathbb P?$$ Note that in this case $n=16843^2$ is not a counterexample (Wolfram Alpha confirms that the congruence does not even hold modulo $16843^9$)...

$\endgroup$
1
14
$\begingroup$

Note that $\displaystyle\binom{n^2}{n} = \frac{1}{(n - 1)!} \frac{n^2 (n^2 - 1) ... (n^2 - (n - 1))}{n} = \frac{1}{(n - 1)!} n (n^2 - 1) ... (n^2 - (n - 1))$

Consider a prime $p > 2$. Then $1, 2, ..., p - 1$ are all invertible modulo $p^4$; thus, so is $(p - 1)!$. Now consider $\displaystyle\binom{p^2}{p} = \frac{1}{(p - 1)!} p (p^2 - 1) ... (p^2 - (p - 1))$.

Define the polynomial $P(x) = x (x^2 - 1) (x^2 - 2) ... (x^2 - (p - 1))$. We wish to reduce $P(x)$ modulo $x^4$. We note that this will only have an $x$ and $x^3$ term since $P$ is odd. The $x$ term will clearly be $(p - 1)! x$; the $x^3$ term will be $-(p - 1)! x^3 \left(\frac{1}1 + \frac{1}2 + \cdots + \frac{1}{p - 1}\right)$. Then mod $p^4$, we have $\displaystyle \binom{p^2}{p} = p - p^3 \left(\frac{1}1 + \frac{1}2 + \cdots+ \frac{1}{p - 1}\right)$ (taking division modulo $p^4$ as well).

Note that when reducing $\mod p$, we have $\frac{1}1 + \frac{1}2 + \cdots + \frac{1}{p - 1} = 1 + 2 + ... + (p - 1)$, since every number from $1$ to $p - 1$ is a unit. And this sum is equal to $\frac{p (p - 1)}{2} \equiv 0 \pmod p$, since $p > 2$. Thus, we see that $\frac{1}1 + \frac{1}2 + \cdots + \frac{1}{p - 1}$ will be divisible by $p$ when the division is done $\mod p^4$ as well.

Thus, we have that for all $p>2$ prime, $\displaystyle \binom{p^2}{p} \equiv p \pmod {p^4}$.

I don't have anything going the other direction yet.

$\endgroup$
2
  • 2
    $\begingroup$ The examples in the other direction might well be as rare as Wieferich primes. $\endgroup$ Commented Aug 6, 2020 at 18:15
  • 1
    $\begingroup$ Examples in the other direction are not expected to occur even by chance.... being equal to $p$ mod $p^4$ has probability $1/p^3$, which converges when summed over the primes. Having checked out to a large value, it’s unlikely any counter examples exist... even if there’s no fundamental reason they couldn’t. $\endgroup$
    – mjqxxxx
    Commented Aug 8, 2020 at 8:15
3
$\begingroup$

Iff $p$ is prime, you'll find that

$$\binom{p^{a+k}}{p^a}\equiv p^k \pmod{p^r}, \text{ for }k<r<8\text{ and }a>0\ .$$

So, for example $$\binom{n^7}{n^5} \equiv n^2 \pmod{n^{3}}$$ would work just as well.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .