Sums of prime powers

Introduction

This page expores patterns in the equation (P1n + P2m) modulo P3, where P1, P2 and P3 are prime numbers.

For an example we can look at P1 = 2, P2 = 3 and P3 = 5.

 

Note that the cells that are divisible by 5 form a pattern.

Explore

You can use the following form to create tables for other combinations of primes (or other numbers). (Note. The table algorithm uses javascript's built-in integers which, at the time of writing, are limited to 9007199254740991 (253 - 1)).

P1 : P2 : P3 : Table Hide

 

Explore Further

We can explore further by working with moduli rather than the values. For powers of a single prime, 'p', when calculating pn mod p2 we see that

pn mod p2 = ((pn-1 mod p2) x p) mod p2.

and

p0 mod p2 = 1.

We can use this to generate a sequence of moduli for a given pair of primes, for instance 3n mod 31 gives:

[1, 3, 9, 27, 19, 26, 16, 17, 20, 29, 25, 13, 8, 24, 10, 30, 28, 22, 4, 12, 5, 15, 14, 11, 2, 6, 18, 23, 7, 21, 1]

Which has 30 members. So 3n mod 31 = 3(n mod 30) mod 31.

Calculate your own sequence: P1 : P2 : Go Clock Hide

 

If you experiment with this custom sequence generator you will discover that the number of members in the sequence is always a factor of (P2 − 1). Which leads to the equation

p1(p2-1) mod p2 = 1.

An equation which is very useful in proving that big numbers aren't prime. Unfortunately it can't be used to prove that big numbers are prime as there are some false positives. If you tried the table generator above you will have noticed that it overflows quite quickly if you choose numbers over 25. Instead we can explore the patterns using these moduli instead.

P1 : P2 : P3 : Table SVG Unit-cell Hide

 

Unit cells

The unit cell is determined by the number of entries in the two remainder series. There are three main possibilities:

1. Both remainder series have the full complement of (p3−1) members. In this case for every member of the P1 series, [P1], there must be a matching member of [P2] such that [P1]i + [P2]j = P3. Click to see an example.
2. If one remainder series, say [P2] has the full complement, but the other, [P1], only has a sub-set, then each member of the smaller set, [P1] will have a partner in [P2], but not vice versa. View .
3. If both remainder series are short of the full complement then there are no easy predictions. Some, for instance 3 and 5 mod 11 produce no matches. 3n mod 11 gives [1, 3, 9, 5, 4] and 5n gives [1, 5, 3, 4, 9]. No pairs of numbers, one from each set add up to a multiple of 11, so there are no solutions to 3n + 5m mod 11 = 0.
   
   Interestingly, this also shows there are no solutions to 3n + 3m mod 11 = 0 or 5n + 5m mod 11 = 0.
   
   Another case, 5 and 17 mod 29 produces the sets [1, 5, 25, 9, 16, 22, 23, 28, 24, 4, 20, 13, 7, 6] and [1, 17, 28, 12], giving a unit cell of 14 × 4  but with only two matches, 1 + 28 and 28 + 1. View . 67n + 101m mod 17 is an interesting case: Show .

 

Hide

Other pages