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}$

  1. n = int(input("n="))
  2. m = int(input("m="))
  3. sum=0;
  4. for k in range(1,n+1):
  5. p=1
  6. for t in range(1,k+1):
  7. p=(p*k) % m
  8. sum=(sum+p) % m
  9. 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$

  1. N = int(input("N="))
  2. p = int(input("p="))
  3. s = int(input("s="))
  4. sum=0;m=p**s;
  5. for r in range(1,p):
  6. for k in range(1,N+1):
  7. P=1
  8. for t in range(1,p*(k-1)+r+1):
  9. P=(P*(p*(k-1)+r)) % m
  10. sum=(sum+P) % m
  11. print(sum, "when r=",r)
This post has been edited 2 times. Last edited by fungarwai, Dec 14, 2021, 12:15 PM

Notable algebra methods with proofs and examples

avatar

fungarwai
Shouts
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! :D

    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

  • :omighty: :omighty:

    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
Tags
About Owner
  • Posts: 859
  • Joined: Mar 11, 2017
Blog Stats
  • Blog created: Sep 15, 2018
  • Total entries: 18
  • Total visits: 5839
  • Total comments: 8
Search Blog
a