Jtdylktuy

I am trying to solve http://www.javaist.com/rosecode/problem-519-Factorial-like-Product-askyear-2018

Restating the problem:
$$R(p,k)=prod_{i=1}^{p-1}(i^k+1) hspace{2 mm} text{mod}hspace{2 mm} p$$

$$S(P,k)=sum_{3le ple P}R(p,k)$$

I need to calculate $R(P,k)$ for $P=10^{10}$ and $k=20181026$

For odd $k$, $R(p,k)$ is $0$. For a fixed prime $p$, $R(p,k)$ is periodic with period $p$. And also $R(p,p-1)=1$.

I am unable to proceed further. Any help will be appreciated.

Notice $k = 2 cdot 2069 cdot 4877 = 2 cdot k'$.

Fix an odd prime $p$, and let $d = (p-1,k')$, so that $k' equiv dx pmod{p-1}$. Since $d$ is the gcd of these two numbers, we have $(x,p-1) = 1$, and thus multiplying by $x$ just permutes the set ${0,...,p-2} bmod{p-1}$, meaning, that for any primitive root $g bmod{p}$,
$$
R(p,k) equiv prod_{i=1}^{p-1}(i^{2k'}+1) equiv prod_{r=0}^{p-2} (g^{2rk'}+1) equiv prod_{r=0}^{p-2}(g^{2drx}+1) equiv prod_{r=0}^{p-2}(g^{2dr}+1) equiv
left( prod_{r=0}^{frac{p-1}{2d}-1} (g^{2dr}+1) right)^{2d} pmod{p}
$$
With the last equivalence since $g^{2dr} = g^{2dr + (p-1)} = g^{2d left( r + frac{p-1}{2d} right)}$.

Note since $p equiv 1 pmod{4}$ iff $-1$ is a quadratic residue $bmod{p}$, we have $R(p,k) = 0$ for all such $p$. Therefore, let $p equiv 3 pmod{4}$, where $-1$ is a nonresidue. Expand the inner product for $R(p,k)$ into elementary symmetric polynomials, $e_n(X)$.

Considering the power sums, we let $X = left{1,g^{2d},g^{4d},...,g^{2dleft(frac{p-1}{2d} - 1right)}right}$, and have, for $n in left{1,...,frac{p-1}{2d}-1 right}$:
$$
p_{n}(X)=sum_{r=0}^{frac{p-1}{2d}-1} g^{2dnr} = frac{g^{2dnleft(frac{p-1}{2d} right)}-1}{g^{2dn}-1}=frac{g^{n(p-1)}-1}{g^{2dn}-1}
$$
As $2d mid p-1$, we have $p ge 2d+1$. For $p>2d+1$, since $2dn le p-(2d+1)$, this implies $p-1 nmid 2dn$, so we have $g^{2dn}-1 notequiv 0 pmod{p}$ while $g^{n(p-1)}-1 equiv 0 pmod{p}$, meaning $p_n(X) equiv 0 pmod{p}$. For $p = 2d+1$, this sum is the empty sum, so is trivially $0$.

Now by Newton's Identities, we have, $ne_n(X) = sum_{i=1}^n (-1)^{i-1}e_{n-i}(X) p_i(X)$, so that $e_n(X) equiv 0 pmod{p}$ for all $n in left{1,...,frac{p-1}{2d} -1 right}$. This means that:

$$
R(p,k) equiv left( left(prod_{r=0}^{frac{p-1}{2d}-1} g^{2dr}right) +1right)^{2d} equiv left(g^{2dleft(1+2+ldots+left(frac{p-1}{2d}-1 right)right)} +1right)^{2d} equiv left(g^{(p-1)left(frac{p-(2d+1)}{4d}right)} + 1 right)^{2d} pmod{p}
$$

Since $p equiv 3 pmod{4}$ and $d$ is odd, we have $p-(1+2d) equiv 3-1-2 equiv 0 pmod{4}$. Therefore $frac{p-(2d+1)}{4d}$ is integral, and thus $R(p,k) equiv 2^{2d} pmod{p}$. Note this same argument works as long as $k'$ is odd, and for any $P$. For odd $k$, as you already noted, the sum is $0$.