modular arithmetic on 1^1+2^2+3^3+...+n^n

by fungarwai, Dec 13, 2021, 1:45 PM

To find the modular residue $1^1+2^2+3^3+\dots+n^n \pmod{p^s}$ ,

the main idea is rewriting $1^1+2^2+3^3+\dots+n^n$ as
$1^1+2^2+\dots+(p-1)^{p-1}+p^p$
$+(p+1)^1+(p+2)^2+\dots+(2p-1)^{2p-1}+(2p)^{2p}+\dots$
$=\sum_{r=1}^{p-1}\sum_{k=1}^N (pk-p+r)^{pk-p+r}+\sum_{k=1}^N (pk)^{pk}+\sum_{k=N+1}^n k^k$

While $s$ is enough small, $\sum_{k=1}^N (pk)^{pk}\pmod{p^s}$ would be simply zero.

$\sum_{k=N+1}^n k^k$ has to be calculated manually. Make it as short as it can.

Here $\sum_{r=1}^{p-1}\sum_{k=1}^N (pk-p+r)^{pk-p+r}\pmod{p^s}$ is the main problem.

$p^{s-1}\mid N\implies \sum_{k=1}^N (pk-p+1)^{pk-p+1} \equiv (1-\frac{p}{2})N\equiv \begin{cases} 0 \pmod{p^s} & p=2\\ N\pmod{p^s} & p\neq 2\end{cases}$

Proof

$\varphi(p^s)=p^{s-1}(p-1)\mid N \Rightarrow \sum_{k=1}^N (pk-p+r)^{pk-p+r} \equiv 0 \pmod{p^s} (2\le r\le p-1)$

Proof

Example

Python program for general cases

input values for n, m to get $\sum_{k=1}^n k^k\pmod{m}$

n = int(input("n="))
m = int(input("m="))
sum=0;
for k in range(1,n+1):
 p=1
 for t in range(1,k+1):
  p=(p*k) % m
 sum=(sum+p) % m
print(sum)

n = int(input("n="))
m = int(input("m="))
sum=0;
for k in range(1,n+1):
 p=1
 for t in range(1,k+1):
  p=(p*k) % m
 sum=(sum+p) % m
print(sum)

input values for N, p, s to get $\sum_{k=1}^N (pk-p+r)^{pk-p+r}\pmod{p^s}$ for $1\le r\le p-1$

N = int(input("N="))
p = int(input("p="))
s = int(input("s="))
sum=0;m=p**s;
for r in range(1,p):
 for k in range(1,N+1):
  P=1
  for t in range(1,p*(k-1)+r+1):
   P=(P*(p*(k-1)+r)) % m
  sum=(sum+P) % m
 print(sum, "when r=",r)

N = int(input("N="))
p = int(input("p="))
s = int(input("s="))
sum=0;m=p**s;
for r in range(1,p):
 for k in range(1,N+1):
  P=1
  for t in range(1,p*(k-1)+r+1):
   P=(P*(p*(k-1)+r)) % m
  sum=(sum+P) % m
 print(sum, "when r=",r)

This post has been edited 2 times. Last edited by fungarwai, Dec 14, 2021, 12:15 PM

Finite difference

number theory

Summation

Comment

U VIEW ATTACHMENTS T PREVIEW J CLOSE PREVIEW rREFRESH

0 Comments

Submit

Nice blog!
by Inconsistent, Mar 18, 2024, 2:41 PM
hey, nice blog! really enjoyed the content here and thank you for this contribution to aops. Sure to subscribe!
by thedodecagon, Jan 22, 2022, 1:33 AM
thanks for this
by jasperE3, Dec 3, 2021, 10:01 PM
I am working as accountant and studying as ACCA student now.
I graduated applied mathematics at bachelor degree in Jinan University but I still have no idea to find a specific job with this..
by fungarwai, Aug 28, 2021, 4:54 AM
Awesome algebra blog
by Euler1728, Mar 22, 2021, 5:37 AM
I wonder if accountants need that kind of math tho
by Hamroldt, Jan 14, 2021, 10:55 AM
Nice!!!!
by Delta0001, Dec 12, 2020, 10:20 AM
this is very interesting i really appericate it
by vsamc, Oct 29, 2020, 4:42 PM
this is god level
by Hamroldt, Sep 4, 2020, 7:48 AM
Super Blog! You are Pr0!
by Functional_equation, Aug 23, 2020, 7:43 AM
Great blog!
by freeman66, May 31, 2020, 5:40 AM
cool thx!
by erincutin, May 18, 2020, 4:55 PM
How so op???
by Williamgolly, Apr 30, 2020, 2:42 PM
Beautiful
by Al3jandro0000, Apr 25, 2020, 3:11 AM
Nice method
by Feridimo, Jan 23, 2020, 5:05 PM
This is nice!
by mufree, May 26, 2019, 6:40 AM
Wow! So much Algebra.
by AnArtist, Mar 15, 2019, 1:19 PM
by AlastorMoody, Feb 9, 2019, 5:17 PM
31415926535897932384626433832795
by lkarhat, Dec 25, 2018, 11:53 PM
rip 0 shouts and 0 comments until now
by harry1234, Nov 17, 2018, 8:56 PM

20 shouts

Notable algebra methods

modular arithmetic on 1^1+2^2+3^3+...+n^n

by fungarwai, Dec 13, 2021, 1:45 PM

0 Comments