A Congruence for Sums of Integer Powers Modulo Products of Distinct Primes

Basic Information

• Paper ID: 2510.10418
• Title: A Congruence for Sums of Integer Powers Modulo Products of Distinct Primes
• Authors: Shao-Yuan Huang, Hsiu-Yu Wu (Department of Mathematics and Information Education, National Taipei University of Education)
• Classification: math.NT (Number Theory)
• Publication Date: October 12, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.10418

Abstract

Let $p_1, p_2, \ldots, p_n$ be distinct primes and $N_n = p_1p_2 \cdots p_n$. The paper proves that for any positive integer $L$ divisible by $\text{lcm}(p_1-1, p_2-1, \ldots, p_n-1)$, and natural numbers $a_i$ satisfying $\gcd(a_i, N_n) = p_i$, there exists the congruence relation: $a_1^L + a_2^L + \cdots + a_n^L \equiv n-1 \pmod{N_n}$. Furthermore, for the cases $n=2,3$, the paper provides complete solutions to the remainder problem for $a^\eta \pmod{N_n}$.

Research Background and Motivation

Importance of the Problem

1. Fundamental Nature of Remainder Problems: Determining remainders of the form $a^\eta \equiv ? \pmod{p_1p_2 \cdots p_n}$ is a classical problem in number theory with widespread applications in cryptography, primality testing, and computational number theory.
2. Limitations of Existing Methods:
   • Fermat's Little Theorem applies only to prime moduli
   • Euler's theorem, while applicable to composite moduli, requires the Euler totient function
   • Handling composite moduli typically requires combining the Chinese Remainder Theorem, making the process complex
3. Need for a Unified Framework: Existing methods lack a unified treatment framework. The paper aims to establish more direct formula systems that enable broader application of these formulas to obtain corresponding remainders.
4. Discovery of New Congruence Properties: The research process uncovered interesting congruence properties regarding sums of prime powers.

Core Contributions

1. Main Theorem: Proves congruence relations for sums of integer powers under moduli that are products of distinct primes, satisfying specific conditions (Theorem 4)
2. Complete Solutions to Remainder Problems: Provides complete formulas for $a^\eta \pmod{N_n}$ in the cases $n=2,3$ (Theorems 3 and 5)
3. Unified Theoretical Framework: Establishes a unified method based on Fermat's Little Theorem, extending several classical remainder formulas
4. Concrete Computational Formulas: Provides directly applicable remainder calculation formulas, avoiding complex Chinese Remainder Theorem computations

Detailed Methodology

Core Theoretical Foundation

The paper is based on the following classical theorems:

• Fermat's Little Theorem: If $p$ is prime, $a \in \mathbb{N}$, and $\gcd(a,p)=1$, then $a^{p-1} \equiv 1 \pmod{p}$
• Euler's Theorem: If $\gcd(a,n)=1$, then $a^{\phi(n)} \equiv 1 \pmod{n}$

Main Results

Theorem 3 (Case $n=2$)

Let $p$ and $q$ be distinct primes, $a \in \mathbb{N}$. Then:

1. If $\gcd(a,pq) = pq$, then $a^\eta \equiv 0 \pmod{pq}$
2. If $\gcd(a,pq) = 1$, then $a^{\text{lcm}(p-1,q-1)\eta} \equiv 1 \pmod{pq}$
3. If $\gcd(a,pq) = q$, then $a^{(p-1)\eta} \equiv qq_p \pmod{pq}$
4. If $\gcd(a,pq) = p$, then $a^{(q-1)\eta} \equiv 1-qq_p \pmod{pq}$

where $q_p$ is the multiplicative inverse of $q$ in $\mathbb{Z}_p$.

Theorem 4 (Main Theorem)

Let $p_1, p_2, \ldots, p_n$ be distinct primes, and $a_1, a_2, \ldots, a_n \in \mathbb{N}$ satisfy $\gcd(a_i, p_1p_2 \cdots p_n) = p_i$. Then for any positive integer $L$ divisible by $\text{lcm}(p_1-1, p_2-1, \ldots, p_n-1)$:

$a_1^L + a_2^L + \cdots + a_n^L \equiv n-1 \pmod{p_1p_2 \cdots p_n}$

Theorem 5 (Case $n=3$)

Let $p < q < r$ be primes, $L = \text{lcm}(p-1, q-1, r-1)$, and assume $qr \equiv 1 \pmod{p}$. Then specific remainder formulas for $a^L$ are provided for various values of $\gcd(a,pqr)$.

Proof Strategy

Proof Strategy for Theorem 3

1. Case Analysis: Discusses four cases based on different values of $\gcd(a,pq)$
2. Application of Fermat's Little Theorem: Utilizes $a^{p-1} \equiv 1 \pmod{p}$ and $a^{q-1} \equiv 1 \pmod{q}$
3. Multiplicative Inverse Calculation: Determines specific remainder values through construction and modular arithmetic properties

Proof Strategy for Theorem 4

1. Mathematical Induction: Performs induction on the number of primes $n$
2. Base Cases: Cases $n=1,2$ are established by previous results
3. Inductive Step: Assumes the statement holds for $n=k$ and proves it for $n=k+1$
4. Key Observation: Utilizes properties of $\gcd$ and applications of Fermat's Little Theorem

Experimental Setup

Verification Examples

Example 1 ($n=2$)

• Parameters: $133 = 7 \times 19$, $L = 18 = \text{lcm}(6,18)$
• Verification Result: $7^{18} + 19^{18} \equiv 77 + 57 \equiv 1 \pmod{133}$

Example 2 ($n=3$)

• Parameters: $66 = 2 \times 3 \times 11$, $L = 10 = \text{lcm}(1,2,10)$
• Verification Result: $2^{10} + 3^{10} + 11^{10} \equiv 34 + 45 + 55 \equiv 2 \pmod{66}$

Example 3 ($n=4$)

• Parameters: $p_1=3, p_2=7, p_3=11, p_4=17$, $L = 240$
• Verification Result: $3^{240\eta} + 7^{240\eta} + 11^{240\eta} + 17^{240\eta} \equiv 3 \pmod{3927}$

Computational Verification

The paper verifies the correctness of theoretical results through concrete numerical calculations, demonstrating the practicality of the formulas.

Experimental Results

Main Results Verification

1. Verification of Theorem 4: Multiple concrete examples verify the main congruence relation
2. Accuracy of Remainder Formulas: Examples 3 and 4 demonstrate detailed applications of Theorems 3 and 5 in concrete calculations
3. Practicality of Formulas: Compared to traditional methods, the new formulas provide more direct computational pathways

Computational Advantages

• Avoidance of Chinese Remainder Theorem: Directly provides remainder formulas without complex CRT calculations
• Unified Treatment Framework: Uses the same theoretical foundation across different cases
• Clear Condition Determination: Clearly determines applicable formulas through $\gcd$ values

Related Work

Classical Number Theory Results

1. Fermat's Little Theorem: The theoretical foundation of the paper
2. Euler's Theorem: Classical method for handling general composite moduli
3. Chinese Remainder Theorem: Traditional tool for handling composite moduli

Innovations of This Paper

1. Direct Formulas: Avoids the complex computational process of CRT
2. New Congruence Properties: Discovers interesting congruence relations for sums of prime powers
3. Complete Case Classification: Provides comprehensive treatment for different $\gcd$ cases

Conclusions and Discussion

Main Conclusions

1. Establishes New Congruence Relations: Proves the core congruence relation in Theorem 4
2. Provides Practical Computational Formulas: Offers complete remainder calculation methods for $n=2,3$
3. Unifies the Theoretical Framework: Establishes a unified treatment method based on Fermat's Little Theorem

Limitations

1. Condition Restrictions: Theorem 5 requires the additional condition $qr \equiv 1 \pmod{p}$
2. Complexity Growth: Formulas become increasingly complex as the number of primes increases
3. Special Cases: Currently provides complete solutions only for $n=2,3$

Future Directions

1. Extension to Larger $n$: Establish complete remainder formulas for cases $n \geq 4$
2. Generalization of Conditions: Investigate whether the additional conditions in Theorem 5 can be relaxed
3. Algorithm Optimization: Develop more efficient computational algorithms

In-Depth Evaluation

Strengths

1. Theoretical Innovation: Discovers new number-theoretic congruence properties with theoretical value
2. Practical Value: Provides directly usable computational formulas, avoiding complex CRT calculations
3. Rigorous Proofs: Employs strict proof methods such as mathematical induction
4. Rich Examples: Verifies theoretical results through multiple concrete examples

Weaknesses

1. Limited Completeness: Provides complete solutions only for $n=2,3$
2. Stringent Conditions: Some results require additional restrictive conditions
3. Difficult Generalization: Technical challenges exist in extending methods to larger $n$

Impact

1. Number Theory Contribution: Provides new perspectives and tools for modular arithmetic theory
2. Application Potential: Has potential applications in cryptography and computational number theory
3. Educational Value: Provides new examples and methods for number theory instruction

Applicable Scenarios

1. Cryptographic Applications: Modular exponentiation in RSA and other public-key cryptosystems
2. Primality Testing: Algorithm optimization based on Fermat's test
3. Computational Number Theory: Numerical computation scenarios requiring efficient modular operations

References

The paper cites classical literature in number theory and cryptography, including:

• Burton's Elementary Number Theory
• Hardy and Wright's An Introduction to the Theory of Numbers
• Menezes et al.'s Handbook of Applied Cryptography
• Original papers on the RSA algorithm, among others

Overall Assessment: This is an innovative paper in the field of number theory that discovers new congruence properties and provides practical computational methods. While improvements are needed in completeness and generalizability, its theoretical contributions and practical value make it a valuable research contribution to the field.