Liste des non concordances : jacobi(n, m)=1 et n non résidu quadratique mod m n m 1 2 9 1 5 9 1 8 9 1 2 15 1 8 15 1 5 21 1 17 21 1 20 21 1 2 25 1 3 25 1 7 25 1 8 25 1 12 25 1 13 25 1 17 25 1 18 25 1 22 25 1 23 25 1 2 33 1 8 33 1 17 33 1 29 33 1 32 33 1 3 35 1 12 35 1 13 35 1 17 35 1 27 35 1 33 35 1 2 39 1 5 39 1 8 39 1 11 39 1 20 39 1 32 39 1 11 45 1 14 45 1 26 45 1 29 45 1 41 45 1 44 45 1 3 49 1 5 49 1 6 49 1 10 49 1 12 49 1 13 49 1 17 49 1 19 49 1 20 49 1 24 49 1 26 49 1 27 49 1 31 49 1 33 49 1 34 49 1 38 49 1 40 49 1 41 49 1 45 49 1 47 49 1 48 49 1 5 51 1 11 51 1 14 51 1 20 51 1 23 51 1 29 51 1 41 51 1 44 51 1 2 55 1 7 55 1 8 55 1 13 55 1 17 55 1 18 55 1 28 55 1 32 55 1 43 55 1 52 55 1 2 57 1 8 57 1 14 57 1 29 57 1 32 57 1 41 57 1 50 57 1 53 57 1 56 57 1 2 63 1 8 63 1 11 63 1 23 63 1 29 63 1 32 63 1 44 63 1 50 63 1 53 63 1 ---------------------------------------------------------- TABLE ---------------------------------------------------------- 63 : x o . x o o . x o x x . o 1 x x . x o o x x o . x o x o . o x x 1 x x x . x o 62 : o . 1 . x 1 x . 1 x 1 x x . o 1 1 x x . x . x 1 . 1 x 1 x x . x o 61 : x x x x x x x x x x x x x x x x x . x x x . x x x 1 x x x . x x o 60 : o o o o o x x o o x o . x o . x . . o x x . x o . o x . o . . x x x . . . o x . x x x o . . . x . x . x . x x o . x o x . o 59 : x x 1 x x . x . 1 x x x x . x x . 1 . x x 1 x x 1 x x x 1 x o . x 58 : o x . x x x . x x . x x . x x x 1 x o . x . x x . x x . x x . x . x o . x x 57 : x o x . x x x o . x x o x o . x x 1 o x x . x o . x o . x x x o x x . o x 1 x o x x . x o 56 : o o x o o 1 x x x o . x o x x x o . x x x x x 1 x o x 1 x x o 1 . x x o 55 : x x . o x . . x x o . x . x . x x x . . x x . o x x . . x . . x x o . . x x . . . . . x x x . 1 . x . . x o . x . . . . . . 54 : o o x o o x x o x . o x x o x x o . x o . x x x x 1 x o x o . x x . o 53 : x x . x 1 . x x x 1 x . x 1 x x x . x . x . x x . x x . x o . 1 x x . 1 52 : o x o . x x x . x o . x x x . x x 1 o x x . x 1 x x . x . x x 1 . x o x x 1 x . x 51 : x o x x x o x x x x o . x x x o x x x o x x x . x x o x x x o . o x x . x o 50 : o . . o . x . 1 o . . . x o . x . . . . . x . o . . . . . x . 1 x x . . . 1 . x . . . o x x . x o . . . . o . 1 . . . . x 1 49 : x x x x x o x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x o x x x x x x x x x x x x x x 48 : o o o . o o o . x o x o o . o x x o 1 x o . x x 1 x x . x o x x o 1 . o x . o x . x o 47 : x . 1 . x 1 x x . 1 x x 1 . x x 1 x x 1 . x . x o 1 . x . . x x 46 : o x x x x x x x x x . x o x x x x x . x x x o x x x x . x . x x 45 : x o x o x . . o x x x . . o . . x x x o x . . o . o . x x x . x . o x . x o . x . . x o . . . 1 . o . . . x . x x x x x x o 44 : o o x x x 1 x o x . x x o x x . o x x x 1 x x o 1 x x 1 x x x . 1 43 : x x . x x x . x x . x x x . x 1 x x . x . x x . x x o . x . x x x 1 x . x 42 : o o . o o o . x x o o x x . o x 1 x o x . x x o x x . x o o x o . x x . x x . x o 41 : x x x x 1 x . x x 1 x x . x x 1 . x 1 x o x 1 x 1 x 1 . 1 x . x x 40 : o x o o x . o x o . x x . x . . x . o . . . x o x x . . x x . . . o x x . x o x . x . x . . . 1 . . x x x o . . . . x . x . 39 : x o x x x o x o x x x . x x x x o x x o x x o . x x o x x x o . x . x x o 38 : o . 1 . x x 1 x o . 1 x 1 x x . x x 1 x o . x . 1 . x . o x . x 37 : x x x . x x x . x x x . x . x x 1 x x . x . x o . x x x . x x . x x . . x 36 : o o o x o x x o x x o x x x x x o x x x x x x x x x x x x x x x x x o x x x x x x x x x x x x x x x x x x x x x x x x x x x 35 : x . . o . o . 1 x . . x x o . x . x . o . x . o x . . x . x . 1 x o . . x . . . . x . o x . . o . . . . . o . . x x . . x o 34 : o x x x x x x x o x . x x x x x x o . x . x x 1 x x x x x . x 33 : x o x . x x o . o x o x x . o x x 1 o x . x x o x 1 x o . x x o x 1 . x o o x . x o 32 : o o . x o 1 . x 1 o x . x 1 x . x o 1 x . 1 . x . x x x . 1 x 1 . x 1 31 : x x x x x x x x x . x x x x x o x . . x x x x 1 x x x . x 30 : o o . o o x . o o . . x x o . x . x . x . . . o x o . x o . . o x x . x x x . . x . . o . . . x . x . . . o . x x . . . . o 29 : x x x x 1 x x x . x x x x x o . 1 x . 1 x x x 1 x x . 1 x x . 1 28 : o x o . x o x x . x o . x x . x x 1 x o x . x o x x x . x . x o . x x 1 x x x x . x x 27 : x o . x o . x x o x . o x x 1 x o . x 1 x x . o x x 1 . o x . o x . x o 26 : o x 1 x x o . x x . 1 x x x o . x . x x o . 1 x 1 x x x . 25 : x x x o x x x x x x x x x x x x x x x x x x x o x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 24 : o o o x o o o x o x x x o x o x o x x o . x o x x o x x 1 x o x . x x x o 23 : x . x 1 . x x x 1 x . x o 1 x x . . x . x x . x x . 1 . x . 1 22 : o x . x x x . o x x . x . x o 1 x x x . x . x . x . x . x o x x . x x 21 : x o x x x o o x x x x x x o x o x x o x x x o . x x x o x o x x . o x x o 20 : o . o o . . x 1 o x . . . o x . . x o 1 x . . o . . . x . x . . . o . . x 1 x x . . x o . . . 1 . 1 . . . x . . x x . x x . 19 : x x x x x x x x x o . x x x x x . x . x 1 x x x . x x . x x 18 : o o . o x o . x o x o . x x 1 o . x o x . o . x x o x x x . x 1 o . x x 17 : x x . x 1 . x 1 x o x . 1 1 x . x 1 x 1 x . x . x 1 . o x x 1 x . 16 : o x o x x x o x x x x x x x o x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 15 : x o . o x x . o x x . . x o . x . . . x x . . o . o . . x . . x x x . . . o . . x x . o . . . x . x . x . x . o . x . x . o 14 : o x o 1 x x x o . . o x x x . x x . x 1 x o x 1 x 1 . x x o 13 : x x x . x x . x o . x x . x 1 x x x . x 1 x x . x . x 1 . x x x x 1 x . x 12 : o o o . o x o . x o x o . o x x x 1 x o . x 1 x x . x o x x 1 . o x . o x . x o 11 : x x x 1 x o x . x . x x . o x x x 1 . x 1 x x 1 x x . 1 10 : o x . o x . . x o . . x . x . . x . . . . . . o x x . . x x . . . o . x . x . x . x . x . . . 1 . . . x x o . . . . . . x . 9 : x o x x x x x o x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 8 : o o . x o 1 . x 1 x . x 1 x . x 1 x . 1 . x . x x x . 1 x 1 . x 1 7 : x x . x o x . x . x x . x 1 x x . x o x x . x . x o . x x 1 x x x . x x 6 : o o x o o x x x . o x x o x x o . x o . x o x x 1 x o x . x x . o 5 : x . x o . . . 1 x x . . . o . . . x x 1 x . . o . . . x . x . . . o . . x 1 . x . . x o . . . 1 . 1 . . . x . . x x . x x . 4 : o x o x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 3 : x o . x o . x x o . o x x 1 x o . x 1 x x . o x x 1 . o . o x . x o 2 : o . x 1 . x 1 x . x 1 . x 1 x . 1 . x . x x x . 1 1 . x 1 1 : x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 0 : o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o : | : | : | : | : | : | 1 5 10 5 20 5 30 5 40 5 50 5 60 5 2 RÉSIDUS QUADRATIQUES il existe x tel que x = b mod n (et b mod n, non nul) ===================== Dans l'ordre des choix effectués : x : b est résidu quadratique mod n o : n est impair et jacobi(b, n) = 0 1 : b est non résidu quadratique et jacobi(b, n) = 1, n impair "." ou " ": b est non résidu quadratique et jacobi(b, n) = -1, n impair