Maths Olympiad Prep

Library / /30 of 37

Number theory Difficulty 8.3 Shortlist Find the answer

Determine whether or not there exists a positive integer kk such that p=6k+1p = 6k+1 is a prime and
(3kk)1(modp).\binom{3k}{k} \equiv 1 \pmod{p}.

A number or a short expression. Spacing and $ signs are ignored.

Solution

To determine whether there exists a positive integer k k such that p=6k+1 p = 6k + 1 is a prime and
(3kk)1(modp), \binom{3k}{k} \equiv 1 \pmod{p},
we proceed as follows:

Let g g be a primitive root modulo p p . By definition, g6k1(modp) g^{6k} \equiv 1 \pmod{p} . For any integer a a such that pa p \nmid a , by Fermat's Little Theorem, we have a6k1(modp) a^{6k} \equiv 1 \pmod{p} . Therefore, a3k1,0, a^{3k} \equiv -1, 0, or 1(modp) 1 \pmod{p} .

Since g g is a primitive root modulo p p , the set {g,g2,,g6k} \{ g, g^2, \ldots, g^{6k} \} is equivalent to {1,2,,6k} \{ 1, 2, \ldots, 6k \} .

Consider the sum
A=i=1k(g6i+1)3k. A = \sum_{i=1}^k (g^{6i} + 1)^{3k}.
This sum can only take values in the set {k,k+1,,k1,k}(modp) \{ -k, -k+1, \ldots, k-1, k \} \pmod{p} .

Expanding A A and arranging by binomial coefficients, we get:
A=j=03k(3kj)[(g6j)k1+(g6k)k2++1]. A = \sum_{j=0}^{3k} \binom{3k}{j} \left[ (g^{6j})^k - 1 + (g^{6k})^{k-2} + \cdots + 1 \right].

For j0,k,2k,3k j \neq 0, k, 2k, 3k , we have (g6j)k1+(g6k)k2++10(modp) (g^{6j})^k - 1 + (g^{6k})^{k-2} + \cdots + 1 \equiv 0 \pmod{p} because (g6j)k10(modp) (g^{6j})^k - 1 \equiv 0 \pmod{p} .

Thus,
Ak((3k0)+(3kk)+(3k2k)+(3k3k))(modp). A \equiv k \left( \binom{3k}{0} + \binom{3k}{k} + \binom{3k}{2k} + \binom{3k}{3k} \right) \pmod{p}.

If there exists a prime p=6k+1 p = 6k + 1 such that (3kk)1(modp) \binom{3k}{k} \equiv 1 \pmod{p} , then
A4k(modp). A \equiv 4k \pmod{p}.

However, this contradicts the earlier result that A A must be in the set {k,k+1,,k1,k}(modp) \{ -k, -k+1, \ldots, k-1, k \} \pmod{p} . Therefore, there is no such prime p p .

The answer is: \boxed{\text{No, there does not exist such a prime } p.}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.