How can we calculate $\displaystyle\sum\limits_{k=1}^{2^{16}} \binom{2k}{k}(3\times 2^{14} +1)^k (k-1)^{2^{16}-1}$ mod $(2^{16} +1)$? I am aware that $2^{16} +1$ is a prime.
Summation mod$ (2^{16} +1)$
4
$\begingroup$
prime-numbers
modular-arithmetic
1 Answers
2
It is congruent to 28673 modulo $2^{16}+1$.
The main problem with evaluating this equation is efficiently calculating binomial coefficients modulo p. Fortunately Lucas' Theorem allows us to do this reasonably efficiently. I implemented this calculation in GAP:
BinomialModP:=function(m,n,p)
local M,N;
M:=[];
N:=[];
while(m>0 or n>0) do
M:=Concatenation([m mod p],M);
N:=Concatenation([n mod p],N);
m:=Int(m/p);
n:=Int(n/p);
od;
return Product([1..Size(M)],i->Binomial(M[i],N[i]) mod p) mod p;
end;;
h:=0;
p:=2^16+1;
for k in [1..p-1] do
b:=BinomialModP(2*k,k,p);
c:=PowerModInt(49153,k,p);
d:=PowerModInt(k-1,65535,p);
inc:=(b*c*d) mod p;
h:=(h+inc) mod p;
# Print("k=",k," inc=",inc," (mod ",p,") h=",h," (mod ",p,")\n");
od;
Print(h,"\n");
which was quite slow (but got there in the end). I also implemented it in C using the GMP "bignum" library (which was much faster):
#include
#include
#include
const unsigned long long int p=65537; // 2^16+1
mpz_t p_GMP;
const unsigned long long int e=65535; // 2^16-1
const unsigned long long int z=49153; // 3*2^14+1
const unsigned long long int second_term[16]={1, 49153, 61441, 64513, 65281, 65473, 65521, 65533, 65536, 16384, 4096, 1024, 256, 64, 16, 4};
// An implementation of Lucas' Theorem; see: http://en.wikipedia.org/wiki/Lucas'_theorem
unsigned long long int binomial_mod_p_lucas(unsigned long long int m, unsigned long long int n) {
mpz_t bin,inc;
mpz_init(bin);
mpz_set_ui(bin,1);
mpz_init(inc);
mpz_set_ui(inc,1);
while(m>0 || n>0) {
mpz_bin_uiui(inc,m%p,n%p);
mpz_mod_ui(inc,inc,p);
mpz_mul(bin,bin,inc);
mpz_mod_ui(bin,bin,p);
m=m/p;
n=n/p;
}
unsigned long long int result=mpz_get_ui(bin);
mpz_clear(bin);
mpz_clear(inc);
return result;
}
unsigned long long int k_minus_one_to_the_e(unsigned long long int k) {
mpz_t pow;
mpz_init(pow);
mpz_set_ui(pow,k-1);
mpz_powm_ui(pow,pow,e,p_GMP);
unsigned long long int result=mpz_get_ui(pow);
mpz_clear(pow);
return result;
}
unsigned long long int main() {
mpz_init(p_GMP);
mpz_set_ui(p_GMP,p);
printf("max unsigned long long int: %llu max possible u-int: %llu\n",ULLONG_MAX,(p-1)*(p-1));
unsigned long long int h=0,inc;
int k;
for(k=1;k<=32768;k++) {
inc=binomial_mod_p_lucas(2*k,k);
inc=(inc*second_term[k%16])%p;
inc=(inc*k_minus_one_to_the_e(k))%p;
h=(h+inc)%p;
// printf("k=%llu inc=%llu (mod %llu) h=%llu (mod %llu)\n",k,inc,p,h,p);
}
printf("found h=%llu (mod %llu).\n",h,p);
mpz_clear(p_GMP);
return 0;
}
Both implementations returned $\equiv 28673 \pmod {65537}$. Two additional simplifications were used in the C code:
- $z:=3 \times 2^{14}+1$ has multiplicative order $16$ modulo $p$ (so I store the 16 values of $z^i \pmod p$ in memory and recall them from there when needed), and
- ${2k \choose k} \equiv 0 \pmod p$ if $2k \geq p$ and $k
(This code is valid only on a 64-bit machine in -std=c99 mode.)