# The magicmodulos

Everybody knows that in order to calculate a+b (mod m) or a*b (mod m), we can calculate a (mod m) and b (mod m) and then do the operation. But if we have 2a (mod m) with a>m, we cant reduce a (mod m) and then calculate 2a (mod m) (mod m).

So, the idea is to introduce such modulos in base b, for wich we have always:

 ba = ba (mod m) (mod m) for all values of a (If a (mod m)=0, we'll take m as exponent, not zero)

These numbers aren't so rare. Here is a table of the first twenty magicmodulos in the first bases :

 n° Base 2 Base 3 Base 4 Base 5 Base 6 Base 7 Base 8 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 6 3 3 4 3 3 4 4 18 4 4 5 5 4 6 5 42 6 6 6 6 6 7 6 54 8 9 8 10 7 8 7 126 12 10 10 14 8 12 8 162 16 12 12 15 9 14 9 294 20 18 16 25 12 18 10 342 24 20 18 30 14 20 11 378 32 21 20 42 16 24 12 486 39 27 24 50 18 28 13 882 40 30 30 70 20 36 14 1026 42 36 32 75 21 40 15 1134 48 42 36 98 24 42 16 1314 60 50 40 110 27 49 17 1458 64 54 42 125 28 52 18 1806 78 60 48 129 32 54 19 2058 80 63 52 150 36 56 20 2394 84 68 54 186 40 60

Remark : the number of magicmodulos asymptotically grows with the size of the base.

But, how can we find such numbers ? It's quite easy ; here is their characteristic property :

 bm+1 (mod m) = b (mod m)

Be careful : don't divide each side by b because b and m aren't necessarily relatively prime.

If the precedent property is true, it can be easily shown by recurrence that :

 ba = ba (mod m) (mod m) for all values of a (a (mod m) <> 0)

Example : Because 1458 is a magicmodulo in base 2, we can easily calculate 24400 (mod 1458) : 4400 = 26 (mod 1458) so 24400 (mod 1458) = 226 (mod 1458) = 40 (mod 1458) and that's all !

Most of the magicmodulos can be predicted. These numbers are magicmodulo in base b :

- every divisor of b (even 1 and b) (proved)

- b*(b+1)n for all values of n (proved)

- b*(b-1)n for all values of n (not proved)

- (b-1)n for all values of n (not proved)

- (b-1)*m if m is magicmodulo in base b (not proved)

- (b+1)*m if m>1 is magicmodulo in base b (not proved)

- bm+1-b if m is magicmodulo in base b (proved)

- u*(b-1) with u= 1,2,6,42 or 1806 (not proved)

These numbers u aren't random : I call them universal magicmodulo because they are magicmodulo in all the bases (proved). I think it exists another bigger universal magicmodulo but it must be >20000000 (tested on my computer). So if you find one of them, please email-me !

The magicmodulos can be used in order to speed up the calculation of binary exponentiations (modpow / powmod) modulo N. Perhaps this would accelerate pseudo-primality tests...

## Similarities and differences with prime numbers

 Prime numbers + pseudoprimes Magicmodulos Characteristic property an = a (mod n) an+1 = a (mod n) "Fabrication" of a bigger n --> (bn-1)/(b-1) (pseudoprime in base b) n --> bn+1-b (in base b)

To be continued...