Determine whether or not there exists a positive integer $k$ such that $p = 6k+1$ is a prime and \[\binom{3k}{k} \equiv 1 \pmod{p}.\]
Problem
Source:
Tags: modular arithmetic, number theory, TST
27.07.2010 02:19
21.12.2010 20:55
Can somebody make more analization to the solution of the problem?
27.02.2017 21:50
My solution: Let the condition hold. Set $f(x)=(1+x)^{3k}$ and select a $g \in \{1, 2, \dots , p-1\}$ with order $k$ modulo $p$ (such a $g$ exists as $k \mid p-1$). Note that $$\frac{f(1)+f(g)+f(g^2)+\dots+f(g^{k-1})}{k} \equiv \sum_{j \ge 0} [x^{jk}] f(x) = \binom{3k}{0}+\binom{3k}{k}+\binom{3k}{2k}+\binom{3k}{3k} \equiv 2+2\binom{3k}{k} \equiv 4 \pmod {p}.$$Since $p=6k+1$ we see that $$(1+x)^{3k}=(1+x)^{\frac{p-1}{2}} \equiv r \pmod {p}$$where $r \in \{-1, 0, 1\}.$ It follows that $$b_1+b_2+\dots+b_k \equiv 4k \pmod {p},$$where $b_i \in \{-1, 0, 1\},$ which is clearly false as the former takes values in the set $\{-k, -k+1, \dots, 0, 1, \dots, k-1, k\}$ and none of these can leave $4k$ as residue modulo $p$ as desired.
27.12.2017 04:11
07.05.2020 02:16
Here is my solution with the Legendre symbol. If $p$ is the prime with $p=6k+1$ such that \[\binom{3k}{k} \equiv 1 \pmod{p}.\]Let $S:=\sum_{n=1}^{p-1}\left( \frac{n^4+n}{p}\right)\implies S\equiv \sum_{n=1}^{p-1}(n^4+n)^{\frac{p-1}{2} }\equiv \sum_{\ell=3k}^{2(p-1)}\binom{3k}{\frac{\ell-3k}{3}} ( \sum_{n=1}^{p-1}n^\ell)\pmod{p}.$ By well-known $:$ $ \sum_{n=1}^{p-1}n^\ell\equiv 0\pmod{p}$ if ${p-1}\nmid \ell$, $ \sum_{n=1}^{p-1}n^\ell\equiv -1\pmod{p}$ if ${p-1}\mid \ell$ So $S\equiv -1-\binom{3k}{k}\equiv -2\pmod{p}$ Since $ p\mid n^4+n \Leftrightarrow n(n+1)(n^2-n+1)\equiv 0 \pmod{p}$ $ \left(\frac{-3}{p}\right)=(-1)^{\frac{p-1}{2}}\left(\frac{3}{p}\right)=(-1)^{\frac{p-1}{2}} (-1)^{\frac{p-1}{2}}\left(\frac{p}{3}\right)=1$ Thus $S$ composed by 3 times 0 and several 1,-1. So $-(p-4)\leq S \leq p-4 \Rightarrow S=-2$, but $S$ have same parity with $p-4$ (contradiction). Thus there doesn’t exist $p$ form $6k+1$ satisfy.
21.02.2021 01:15
No. Work in $\mathbb{F}_p$. Observe that \[1+3\sum_{x\ne 0, x^{2k}=1}\left(\frac{1+x}{p}\right)=1+\sum_{x\ne 0}(1+x^3)^{3k}=\sum_x (1+x^3)^{3k}=\sum_i \binom{3k}{i}\sum_x x^{3i} = \binom{3k}{2k}\cdot (-1).\]If we have $\binom{3k}{k}=1$, we would get \[-2=3\sum_{x\ne 0, x^{2k}=1}\left(\frac{1+x}{p}\right)\implies 4k=\sum_{x\ne 0, x^{2k}=1}\left(\frac{1+x}{p}\right).\]This is absurd because the latter sum differs by at most $\pm 2k$ from $0$, so we are done.
06.08.2021 22:09
In fact, there exist integers $a, b$ such that $p=a^2+3b^2$, $a\equiv 1\pmod{3}$, and \[\binom{3k}{k}\equiv 2a\pmod{p}.\]It readily follows that $\binom{3k}{k}\not\equiv 1\pmod{p}$.
24.12.2021 17:17
a1267ab wrote: In fact, there exist integers $a, b$ such that $p=a^2+3b^2$, $a\equiv 1\pmod{3}$, and \[\binom{3k}{k}\equiv 2a\pmod{p}.\]It readily follows that $\binom{3k}{k}\not\equiv 1\pmod{p}$. That seems right but can u show me how to get that? thanks
23.10.2024 07:00
It is indeed a well-known trick until now(yesterday I solved it in 10 minutes), but I wonder how hard it is in 2010, did anyone managed solving this? In my proof $\equiv$ is under mod $p.$ We consider the number of $\{(x,y)\in\mathbb F_p^2:x^2+y^3\equiv 1\},$ say $N.$ On one hand, take primitive root $g,$ \begin{align*}N&=\sum_{y\in\mathbb F_p}\left[1+\left(\frac {1-y^3}p\right)\right]\\&\equiv p+1+3\sum_{j=0}^{2k-1}(1-g^{3j})^{3k}\\&\equiv 1+3\sum_{j=0}^{2k-1}\sum_{t=0}^{3k}\binom{3k}t(-1)^tg^{3jt}\\&=1+3\sum_{t=0}^{3k}\binom{3k}t(-1)^t\sum_{j=0}^{2k-1}g^{3jt}\\&\equiv 1+3\cdot 2k+3\binom{3k}{2k}(-1)^{2k}\cdot 2k\\&\equiv -\binom{3k}k\equiv -1.\end{align*}On the other hand $N<2p-1,$ $N=p-1.$ However there are exactly three $y\in\mathbb F_p$ such that $y^3\equiv 1,$ therefore there are $\frac{p-4}2$ number of $y$ that $\left(\frac {1-y^3}p\right)=1,$ which leads to contradiction since $p$ is odd.$\Box$ Remark. Using Jacobi Sum we can show that $|N-p|\le 2\sqrt p.$
27.10.2024 11:48
..........
09.11.2024 03:50
Overkill? See that this is obvious for $p=7$ and $13$. So assume $p \geq 19$. Now see that \[\sum_{x=0}^{p-1} \left(\frac{1+x^3}p \right) \equiv \sum_{x=0}^{p-1} (1+x^3)^{3k} \equiv -1-2 \binom{3k}k \equiv p-3 \pmod p\]Now see that there exists three different $x$ such that $p \mid x^3+1$. And see hence in this summation, if we look at the other $p-3$ elements, we get that all of them have Legendre symbol values as $1$. Now I really did not want to do this but it is late in the night so... Consider this Elliptic curve in $\mathbb{F}_p$ \[1+x^3=y^2\]and we count the number of solutions $(x,y)$ where $y \neq 0$. See that this is exactly $2p-6$. But by Hasse-Weil Bound we get that the number of solutions is maximum $p+2 \sqrt{p}+1$. And so we get that \[p+2\sqrt{p}+1 \geq 2p-6 \implies p \leq 15\]And so we get a contradiction.