4
$\begingroup$

I am not sure if the following result is known or an equivalent result is known. I think, if the result holds then this could be used an elementary number theory exercise.

Let $k \in \mathbb{Z} \setminus \{0\}$ be fixed. For $n\in \mathbb{N} $ , let $A_{n,k}=[a^{nk}_{ij}]$ be a $n\times n$ matrix such that $$ a^{nk}_{ij}= \begin{cases} i & i= j \\ k & \text{otherwise} \end{cases} $$ As a matrix, $A_{n,k}$ has the following form $$ A_{n,k}=\left[ \begin{matrix} 1 & k & \ldots & k\\ k & 2 & \ldots & k\\ \vdots & \vdots & \ddots & \vdots\\ k & k &\ldots & n \end{matrix} \right] $$ Conjecture: Let $n\geq |k|$. If $k$ is odd , then $n$ is prime number if and only if $$|{\det(A_{n,k})}|\equiv -|{k}| \mod n $$ and if $k$ is even then $n$ is prime if and only if $$|{\det(A_{n,k})}|\equiv -k \mod n .$$

It is easy to figure out for $k\geq 1$ , $\det A_{n,k}=(k-1)!(n-k)!$ . Thus, for $k=1$, you basically get $\det A_{n,1}=(n-1)!$ which is equivalent to Wilson's theorem. For $k>1$, we get $n$ prime iff $(k-1)!(n-k)!\equiv (-1)^k \mod n.$ I wrote a Matlab code to check and it seems to be true. Does anyone have a counterexample or know how to prove it? The Gauss's generalization of Wilson's theorem seem to be related to this but that only considers(as far as I know) integers less than and that are co-prime to $n$.

P. S. For $k=-1$, I calculated the determinant in a non trivial way and got $\det A_{n,-1}={n!\big(n-(1+n)(\mathcal{H}_n-1)\big)}$ where $\mathcal{H}_n$ is the $n$th harmonic number so the determinant of this matrix seem to relate the $n$-harmonic number with prime numbers as well.

$\endgroup$
3
$\begingroup$

This is for the case $k>0$. If $n$ is prime, then it can be seen from this post that

$${{n-1}\choose {k-1}}=(-1)^{k-1} \pmod n.$$ Combining with $(n-1)!=-1 \pmod n$, one gets $(k-1)!(n-k)!=(-1)^k$ for all $1\leq k \leq n$.

For the converse, suppose $(k-1)!(n-k)!=(-1)^k \pmod n$ for some $1\leq k\leq n$. We claim that $n$ must be prime. On the contrary, suppose $n$ is composite and let $p$ be a prime factor of $n$. If $k>p$, then $(k-1)!$ is divisible by $p$. If $k\leq p$, then $n-k\geq n-p \geq p$ and so $(n-k)!$ is divisibly by $p$. In either case $(k-1)!(n-k)!=0 \pmod p$ contradicting the assumption.

For $k<0$, let $l=-k$ and use this post to get $$\det A=\prod_{i=1}^n(i+l)-l\sum_{i=1}^n\prod_{j\neq i}(j+l)\equiv -l \prod_{j\neq n-l}(j+l) \pmod n,$$ since all other terms have a factor of $n$. One has for both odd and even $k$ $$-l\prod_{j\neq n-l}(j+l)=-l(1+l)\cdots(n-1)(n+1)\cdots(n+l)\equiv -l(l+1)\cdots(n-1)(1)(2)\cdots (l)\equiv-l(n-1)! \equiv k(n-1)! \pmod n.$$

Therefore, $\det A \equiv -k \pmod n$ if and only if $n$ is prime by Wilson's theorem.

$\endgroup$
  • $\begingroup$ Great! I am surprised the statement holds !. $\endgroup$ – Basanta R Pahari Sep 23 '18 at 17:32

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.