roots mod n

• root.php
  

• 2
• 3
  • 2 ** 2 = 1: 2,1
• 4
  • 2 ** 2 = 0: 2,0
  • 3 ** 2 = 1: 3,1
• 5
  • 2 ** 4 = 1: 2,4,3,1
  • 3 ** 4 = 1: 3,4,2,1
  • 4 ** 2 = 1: 4,1
• 6
  • 2 ** 3 = 2: 2,4,2
  • 3 ** 2 = 3: 3,3
  • 4 ** 2 = 4: 4,4
  • 5 ** 2 = 1: 5,1
• 7
  • 2 ** 3 = 1: 2,4,1
  • 3 ** 6 = 1: 3,2,6,4,5,1
  • 4 ** 3 = 1: 4,2,1
  • 5 ** 6 = 1: 5,4,6,2,3,1
  • 6 ** 2 = 1: 6,1
• 8
  • 2 ** 3 = 0: 2,4,0
  • 3 ** 2 = 1: 3,1
  • 4 ** 2 = 0: 4,0
  • 5 ** 2 = 1: 5,1
  • 6 ** 3 = 0: 6,4,0
  • 7 ** 2 = 1: 7,1
• 9
  • 2 ** 6 = 1: 2,4,8,7,5,1
  • 3 ** 2 = 0: 3,0
  • 4 ** 3 = 1: 4,7,1
  • 5 ** 6 = 1: 5,7,8,4,2,1
  • 6 ** 2 = 0: 6,0
  • 7 ** 3 = 1: 7,4,1
  • 8 ** 2 = 1: 8,1
• 10
  • 2 ** 5 = 2: 2,4,8,6,2
  • 3 ** 4 = 1: 3,9,7,1
  • 4 ** 3 = 4: 4,6,4
  • 5 ** 2 = 5: 5,5
  • 6 ** 2 = 6: 6,6
  • 7 ** 4 = 1: 7,9,3,1
  • 8 ** 5 = 8: 8,4,2,6,8
  • 9 ** 2 = 1: 9,1
• 11
  • 2 ** 10 = 1: 2,4,8,5,10,9,7,3,6,1
  • 3 ** 5 = 1: 3,9,5,4,1
  • 4 ** 5 = 1: 4,5,9,3,1
  • 5 ** 5 = 1: 5,3,4,9,1
  • 6 ** 10 = 1: 6,3,7,9,10,5,8,4,2,1
  • 7 ** 10 = 1: 7,5,2,3,10,4,6,9,8,1
  • 8 ** 10 = 1: 8,9,6,4,10,3,2,5,7,1
  • 9 ** 5 = 1: 9,4,3,5,1
  • 10 ** 2 = 1: 10,1
• 12
  • 2 ** 4 = 4: 2,4,8,4
  • 3 ** 3 = 3: 3,9,3
  • 4 ** 2 = 4: 4,4
  • 5 ** 2 = 1: 5,1
  • 6 ** 2 = 0: 6,0
  • 7 ** 2 = 1: 7,1
  • 8 ** 3 = 8: 8,4,8
  • 9 ** 2 = 9: 9,9
  • 10 ** 3 = 4: 10,4,4
  • 11 ** 2 = 1: 11,1
• 13
  • 2 ** 12 = 1: 2,4,8,3,6,12,11,9,5,10,7,1
  • 3 ** 3 = 1: 3,9,1
  • 4 ** 6 = 1: 4,3,12,9,10,1
  • 5 ** 4 = 1: 5,12,8,1
  • 6 ** 12 = 1: 6,10,8,9,2,12,7,3,5,4,11,1
  • 7 ** 12 = 1: 7,10,5,9,11,12,6,3,8,4,2,1
  • 8 ** 4 = 1: 8,12,5,1
  • 9 ** 3 = 1: 9,3,1
  • 10 ** 6 = 1: 10,9,12,3,4,1
  • 11 ** 12 = 1: 11,4,5,3,7,12,2,9,8,10,6,1
  • 12 ** 2 = 1: 12,1
• 14
  • 2 ** 4 = 2: 2,4,8,2
  • 3 ** 6 = 1: 3,9,13,11,5,1
  • 4 ** 4 = 4: 4,2,8,4
  • 5 ** 6 = 1: 5,11,13,9,3,1
  • 6 ** 3 = 6: 6,8,6
  • 7 ** 2 = 7: 7,7
  • 8 ** 2 = 8: 8,8
  • 9 ** 3 = 1: 9,11,1
  • 10 ** 7 = 10: 10,2,6,4,12,8,10
  • 11 ** 3 = 1: 11,9,1
  • 12 ** 7 = 12: 12,4,6,2,10,8,12
  • 13 ** 2 = 1: 13,1
• 15
  • 2 ** 4 = 1: 2,4,8,1
  • 3 ** 5 = 3: 3,9,12,6,3
  • 4 ** 2 = 1: 4,1
  • 5 ** 3 = 5: 5,10,5
  • 6 ** 2 = 6: 6,6
  • 7 ** 4 = 1: 7,4,13,1
  • 8 ** 4 = 1: 8,4,2,1
  • 9 ** 3 = 9: 9,6,9
  • 10 ** 2 = 10: 10,10
  • 11 ** 2 = 1: 11,1
  • 12 ** 5 = 12: 12,9,3,6,12
  • 13 ** 4 = 1: 13,4,7,1
  • 14 ** 2 = 1: 14,1
• 16
  • 2 ** 4 = 0: 2,4,8,0
  • 3 ** 4 = 1: 3,9,11,1
  • 4 ** 2 = 0: 4,0
  • 5 ** 4 = 1: 5,9,13,1
  • 6 ** 4 = 0: 6,4,8,0
  • 7 ** 2 = 1: 7,1
  • 8 ** 2 = 0: 8,0
  • 9 ** 2 = 1: 9,1
  • 10 ** 4 = 0: 10,4,8,0
  • 11 ** 4 = 1: 11,9,3,1
  • 12 ** 2 = 0: 12,0
  • 13 ** 4 = 1: 13,9,5,1
  • 14 ** 4 = 0: 14,4,8,0
  • 15 ** 2 = 1: 15,1
• 17
  • 2 ** 8 = 1: 2,4,8,16,15,13,9,1
  • 3 ** 16 = 1: 3,9,10,13,5,15,11,16,14,8,7,4,12,2,6,1
  • 4 ** 4 = 1: 4,16,13,1
  • 5 ** 16 = 1: 5,8,6,13,14,2,10,16,12,9,11,4,3,15,7,1
  • 6 ** 16 = 1: 6,2,12,4,7,8,14,16,11,15,5,13,10,9,3,1
  • 7 ** 16 = 1: 7,15,3,4,11,9,12,16,10,2,14,13,6,8,5,1
  • 8 ** 8 = 1: 8,13,2,16,9,4,15,1
  • 9 ** 8 = 1: 9,13,15,16,8,4,2,1
  • 10 ** 16 = 1: 10,15,14,4,6,9,5,16,7,2,3,13,11,8,12,1
  • 11 ** 16 = 1: 11,2,5,4,10,8,3,16,6,15,12,13,7,9,14,1
  • 12 ** 16 = 1: 12,8,11,13,3,2,7,16,5,9,6,4,14,15,10,1
  • 13 ** 4 = 1: 13,16,4,1
  • 14 ** 16 = 1: 14,9,7,13,12,15,6,16,3,8,10,4,5,2,11,1
  • 15 ** 8 = 1: 15,4,9,16,2,13,8,1
  • 16 ** 2 = 1: 16,1
• 18
  • 2 ** 7 = 2: 2,4,8,16,14,10,2
  • 3 ** 3 = 9: 3,9,9
  • 4 ** 4 = 4: 4,16,10,4
  • 5 ** 6 = 1: 5,7,17,13,11,1
  • 6 ** 2 = 0: 6,0
  • 7 ** 3 = 1: 7,13,1
  • 8 ** 3 = 8: 8,10,8
  • 9 ** 2 = 9: 9,9
  • 10 ** 2 = 10: 10,10
  • 11 ** 6 = 1: 11,13,17,7,5,1
  • 12 ** 2 = 0: 12,0
  • 13 ** 3 = 1: 13,7,1
  • 14 ** 7 = 14: 14,16,8,4,2,10,14
  • 15 ** 3 = 9: 15,9,9
  • 16 ** 4 = 16: 16,4,10,16
  • 17 ** 2 = 1: 17,1
• 19
  • 2 ** 18 = 1: 2,4,8,16,13,7,14,9,18,17,15,11,3,6,12,5,10,1
  • 3 ** 18 = 1: 3,9,8,5,15,7,2,6,18,16,10,11,14,4,12,17,13,1
  • 4 ** 9 = 1: 4,16,7,9,17,11,6,5,1
  • 5 ** 9 = 1: 5,6,11,17,9,7,16,4,1
  • 6 ** 9 = 1: 6,17,7,4,5,11,9,16,1
  • 7 ** 3 = 1: 7,11,1
  • 8 ** 6 = 1: 8,7,18,11,12,1
  • 9 ** 9 = 1: 9,5,7,6,16,11,4,17,1
  • 10 ** 18 = 1: 10,5,12,6,3,11,15,17,18,9,14,7,13,16,8,4,2,1
  • 11 ** 3 = 1: 11,7,1
  • 12 ** 6 = 1: 12,11,18,7,8,1
  • 13 ** 18 = 1: 13,17,12,4,14,11,10,16,18,6,2,7,15,5,8,9,3,1
  • 14 ** 18 = 1: 14,6,8,17,10,7,3,4,18,5,13,11,2,9,12,16,15,1
  • 15 ** 18 = 1: 15,16,12,9,2,11,13,5,18,4,3,7,10,17,8,6,14,1
  • 16 ** 9 = 1: 16,9,11,5,4,7,17,6,1
  • 17 ** 9 = 1: 17,4,11,16,6,7,5,9,1
  • 18 ** 2 = 1: 18,1
• 20
  • 2 ** 6 = 4: 2,4,8,16,12,4
  • 3 ** 4 = 1: 3,9,7,1
  • 4 ** 3 = 4: 4,16,4
  • 5 ** 2 = 5: 5,5
  • 6 ** 3 = 16: 6,16,16
  • 7 ** 4 = 1: 7,9,3,1
  • 8 ** 5 = 8: 8,4,12,16,8
  • 9 ** 2 = 1: 9,1
  • 10 ** 2 = 0: 10,0
  • 11 ** 2 = 1: 11,1
  • 12 ** 5 = 12: 12,4,8,16,12
  • 13 ** 4 = 1: 13,9,17,1
  • 14 ** 4 = 16: 14,16,4,16
  • 15 ** 3 = 15: 15,5,15
  • 16 ** 2 = 16: 16,16
  • 17 ** 4 = 1: 17,9,13,1
  • 18 ** 6 = 4: 18,4,12,16,8,4
  • 19 ** 2 = 1: 19,1
• 21
  • 2 ** 6 = 1: 2,4,8,16,11,1
  • 3 ** 7 = 3: 3,9,6,18,12,15,3
  • 4 ** 3 = 1: 4,16,1
  • 5 ** 6 = 1: 5,4,20,16,17,1
  • 6 ** 3 = 6: 6,15,6
  • 7 ** 2 = 7: 7,7
  • 8 ** 2 = 1: 8,1
  • 9 ** 4 = 9: 9,18,15,9
  • 10 ** 6 = 1: 10,16,13,4,19,1
  • 11 ** 6 = 1: 11,16,8,4,2,1
  • 12 ** 7 = 12: 12,18,6,9,3,15,12
  • 13 ** 2 = 1: 13,1
  • 14 ** 3 = 14: 14,7,14
  • 15 ** 2 = 15: 15,15
  • 16 ** 3 = 1: 16,4,1
  • 17 ** 6 = 1: 17,16,20,4,5,1
  • 18 ** 4 = 18: 18,9,15,18
  • 19 ** 6 = 1: 19,4,13,16,10,1
  • 20 ** 2 = 1: 20,1
• 22
  • 2 ** 11 = 2: 2,4,8,16,10,20,18,14,6,12,2
  • 3 ** 5 = 1: 3,9,5,15,1
  • 4 ** 6 = 4: 4,16,20,14,12,4
  • 5 ** 5 = 1: 5,3,15,9,1
  • 6 ** 11 = 6: 6,14,18,20,10,16,8,4,2,12,6
  • 7 ** 10 = 1: 7,5,13,3,21,15,17,9,19,1
  • 8 ** 11 = 8: 8,20,6,4,10,14,2,16,18,12,8
  • 9 ** 5 = 1: 9,15,3,5,1
  • 10 ** 3 = 10: 10,12,10
  • 11 ** 2 = 11: 11,11
  • 12 ** 2 = 12: 12,12
  • 13 ** 10 = 1: 13,15,19,5,21,9,7,3,17,1
  • 14 ** 6 = 14: 14,20,16,4,12,14
  • 15 ** 5 = 1: 15,5,9,3,1
  • 16 ** 6 = 16: 16,14,4,20,12,16
  • 17 ** 10 = 1: 17,3,7,9,21,5,19,15,13,1
  • 18 ** 11 = 18: 18,16,2,14,10,4,6,20,8,12,18
  • 19 ** 10 = 1: 19,9,17,15,21,3,13,5,7,1
  • 20 ** 6 = 20: 20,4,14,16,12,20
  • 21 ** 2 = 1: 21,1
• 23
  • 2 ** 11 = 1: 2,4,8,16,9,18,13,3,6,12,1
  • 3 ** 11 = 1: 3,9,4,12,13,16,2,6,18,8,1
  • 4 ** 11 = 1: 4,16,18,3,12,2,8,9,13,6,1
  • 5 ** 22 = 1: 5,2,10,4,20,8,17,16,11,9,22,18,21,13,19,3,15,6,7,12,14,1
  • 6 ** 11 = 1: 6,13,9,8,2,12,3,18,16,4,1
  • 7 ** 22 = 1: 7,3,21,9,17,4,5,12,15,13,22,16,20,2,14,6,19,18,11,8,10,1
  • 8 ** 11 = 1: 8,18,6,2,16,13,12,4,9,3,1
  • 9 ** 11 = 1: 9,12,16,6,8,3,4,13,2,18,1
  • 10 ** 22 = 1: 10,8,11,18,19,6,14,2,20,16,22,13,15,12,5,4,17,9,21,3,7,1
  • 11 ** 22 = 1: 11,6,20,13,5,9,7,8,19,2,22,12,17,3,10,18,14,16,15,4,21,1
  • 12 ** 11 = 1: 12,6,3,13,18,9,16,8,4,2,1
  • 13 ** 11 = 1: 13,8,12,18,4,6,9,2,3,16,1
  • 14 ** 22 = 1: 14,12,7,6,15,3,19,13,21,18,22,9,11,16,17,8,20,4,10,2,5,1
  • 15 ** 22 = 1: 15,18,17,2,7,13,11,4,14,3,22,8,5,6,21,16,10,12,19,9,20,1
  • 16 ** 11 = 1: 16,3,2,9,6,4,18,12,8,13,1
  • 17 ** 22 = 1: 17,13,14,8,21,12,20,18,7,4,22,6,10,9,15,2,11,3,5,16,19,1
  • 18 ** 11 = 1: 18,2,13,4,3,8,6,16,12,9,1
  • 19 ** 22 = 1: 19,16,5,3,11,2,15,9,10,6,22,4,7,18,20,12,21,8,14,13,17,1
  • 20 ** 22 = 1: 20,9,19,12,10,16,21,6,5,8,22,3,14,4,11,13,7,2,17,18,15,1
  • 21 ** 22 = 1: 21,4,15,16,14,18,10,3,17,12,22,2,19,8,7,9,5,13,20,6,11,1
  • 22 ** 2 = 1: 22,1

End root.php

root.php

<html>
<?php
require_once('env.php');
outBegin('roots mod n');

outUL();
for ($i=2; $i <24; $i++) {
    outLi($i);
    outUL();
    for ($k=2;$k<$i;$k++) {
        $t = ",$k";
        $v=$k;
        for ($e=2; $e<100; $e++) {
            $v = $v * $k % $i;
            $t .= ",$v";
            if ($v <= 1 or strpos($t, ",$v,") !== false)
                break;
        }
        outLi("$k ** $e = $v:", substr($t, 1));
    }
    outULEnd();
}
outULEnd();
outEnd(__file__);

?>