Determine all pairs of positive integers(a,p) where p is a prime and

(a modp)+(a mod2p)+(a mod3p)+(a mod4p)=a+p

Cases:

a < p:

4a = a + p
3a = p 
Solution 1: a=1, p=3

a = p:

3p = 2p
not possible

p < a < 2p:

4a - p = a + p
3a = 2p
p=3, a=2 violates the assumption p < a < 2p.

a = 2p

2a = a + p
a = p
violates the assumption a=2p

2p < a < 3p:

4a - 4p = a + p
3a = 5p
p=3, a=5 violates the assumption 2p < a < 3p

a = 3p:

a - 2p + a = a + p
a = 3p
Tautology; works with any prime p
Solution 2: 3p, p where p is any prime

3p < a < 4p:

4a - 3p - 2p - 3p = a + p
3a = 9p
a = 3p violates the assumption 3p < a < 4p

a = 4p:

a - 3p = a + p
4p = 0
no solution

4p < a:

Let a = kp + b

Here we need to get down to subcases of k mod 12. It sounds a bit daunting. Rather than that we'll try a brute force approach for the first ten primes:

DEFDBL A-Z
CLS
DATA 2,3,5,7,11,13,17,19,23,29

FOR i = 1 TO 10: READ pr(i): NEXT

FOR prNum = 1 TO 10
p = pr(prNum)
FOR a = 1 TO 100000
  lhs = a MOD p + a MOD (2 * p) + a MOD (3 * p) + a MOD (4 * p)
  IF lhs = a + p THEN PRINT a, p
NEXT
NEXT

which finds:

a             p
6             2
1             3
9             3
17            3
15            5
21            7
33            11
39            13
51            17
57            19
69            23
93            31

which includes only one pair we didn't get analytically: (17,3).

In sum: (1,3), (17,3) and (3p,p) for all prime p.

This continues even if the primes are extended to inclued up to 113.

Edited on December 28, 2012, 9:34 pm

Posted by Charlie on 2012-12-28 21:15:36