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 2^{a} (mod m) with a>m, we cant reduce a (mod m) and
then calculate 2^{a (mod m)} (mod m).
So, the idea is to introduce such modulos in base b, for wich we have always:
b^{a} = b^{a (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 :
b^{m+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 :
b^{a} = b^{a (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 2^{4400} (mod 1458) : 4400 = 26 (mod 1458) so 2^{4400} (mod 1458) = 2^{26} (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*(b1)^{n} for all values of n (not proved)
 (b1)^{n} for all values of n (not proved)
 (b1)*m if m is magicmodulo in base b (not proved)
 (b+1)*m if m>1 is magicmodulo in base b (not proved)
 b^{m+1}b if m is magicmodulo in base b (proved)
 u*(b1) 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 emailme !
The magicmodulos can be used in order to speed up the calculation of binary exponentiations (modpow / powmod) modulo N. Perhaps this would accelerate pseudoprimality tests...
Prime numbers + pseudoprimes

Magicmodulos


Characteristic property 
a^{n} = a (mod n)

a^{n+1} = a (mod n)

"Fabrication" of a bigger 
n > (b^{n}1)/(b1) (pseudoprime in base
b)

n > b^{n+1}b (in base b)

To be continued...