Computing solutions to the congruence 1ⁿ + 2ⁿ + + n^n p n

DOI10.1016/J.DAM.2018.05.022MaRDI QIDQ2201763zbMATHOpenAlexDBLPWikidataFDO

Authors Max A. Alekseyev, José María Grau, Antonio M. Oller Marcén

Publication date 17 September 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.02407

zbMATH Keywords

algorithmpower sumsprimary pseudoperfect numbers

Mathematics Subject Classification ID

Congruences in many variables (11D79) Computer solution of Diophantine equations (11Y50)

Abstract: It is well-known that the congruence $su{m}_{i=1}^n{i}^{n}equiv1pmodn$ has exactly five solutions: $1,2,6,42,1806$. In this work, we characterize the solutions to the congruence $1^n+2^n+dotsb+n^{n}equivppmodn$ for every prime $p$. This characterization leads to an algorithm for computing all such solutions, when there is a finite number of them. More generally, our algorithm enables computing all the solutions below a much higher bound as compared to what can be achieved by a naive exhaustive search.

Recommendations

• Solutions of the congruence \(1+2^{f(n)}+\ldots +n^{f(n)}\equiv 0 \pmod n\)
• scientific article; zbMATH DE number 4210234
• scientific article; zbMATH DE number 991673
• Counting the solutions of \(\lambda_1 x_1^{k_1} + \dots + \lambda_t x_t^{k_t} \equiv c \bmod n\)
• Algorithms for enumeration problem of linear congruence modulo \(m\) as sum of restricted partition numbers

Cites work

• scientific article; zbMATH DE number 3679908 (Why is no real title available?)
• scientific article; zbMATH DE number 3069345 (Why is no real title available?)
• Giuga's Conjecture on Primality
• On the congruence \(1^m + 2^m + \ldots + m^m\equiv n \bmod m\) with \(n\mid m\)
• On the equation $\sum_{p|N}\frac1p+\frac1N = 1$, pseudoperfect numbers, and perfectly weighted graphs
• Power-sum denominators
• Reducing the Erdős–Moser Equation 1 n + 2 n + ⋯ + kn = (k + 1) n Modulo k and k 2
• Solutions of the congruence \(1+2^{f(n)}+\ldots +n^{f(n)}\equiv 0 \pmod n\)

Cited in

(5)

• A new solution to the equation \(\tau(p)\equiv 0\pmod p\)
• scientific article; zbMATH DE number 3417539 (Why is no real title available?)
• Reducing the Erdős–Moser Equation 1 n + 2 n + ⋯ + kn = (k + 1) n Modulo k and k 2
• Solutions of the congruence 𝑎^{𝑝-1}≡1 (mod 𝑝^{𝑟})
• Solutions of the congruence \(1+2^{f(n)}+\ldots +n^{f(n)}\equiv 0 \pmod n\)

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Computing solutions to the congruence \(1^n + 2^n + \ldots + n^n \equiv p \pmod n\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2201763)