Don't take life too seriously: it's just a temporary situation

Simbolo di Jacobi

Funzioni  Teoria dei numeri 

Il simbolo di Jacobi è una funzione, indicata con Simbolo di Jacobi, definita per m e n interi positivi come Formula per la definizione del simbolo di Jacobi, dove Simbolo di Legendre è il simbolo di LegendreScomposizione in fattori primi di m è la scomposizione di m in fattori primi. Per convenzione Definizione del simbolo di Jacobi (n | 1).

La definizione è talvolta estesa, definendo Definizione del simbolo di Jacobi (n | m) se m e n hanno un divisore comune maggiore di 1.

 

E’ la generalizzazione del simbolo di Legendre al caso di m composto; coincide con esso se m è primo, tuttavia mentre se Simbolo di Jacobi (n | m) = –1, n non è residuo quadratico modulo m, se Simbolo di Jacobi (n | m) = 1 non è detto che n sia un residuo quadratico modulo m: questo accade solo se n è residuo quadratico modulo ogni primo che divida m.

 

Dalla definizione segue che:

  • Valore del simbolo di Jacobi (1 | m), per m > 1;

  • Valore del simbolo di Jacobi (n | n);

  • Valore del simbolo di Jacobi (a | m), se ab mod m;

 

E’ completamente moltiplicativo, sia rispetto al primo argomento, che rispetto al secondo: Simbolo di Jacobi come funzione moltiplicativa rispetto al primo argomento, Simbolo di Jacobi come funzione moltiplicativa rispetto al secondo argomento.

 

Alcune proprietà, valide per m dispari:

  • Valore del simbolo di Jacobi (–1 | m)
  • Valore del simbolo di Jacobi (2 | m)
  • Valore del simbolo di Jacobi (n^2 | m), se m e n sono primi tra loro.

 

Permette di estendere il teorema di reciprocità quadratica a qualsiasi coppia di numeri naturali dispari m e n: Teorema di reciprocità quadratica, espressa tramite il simbolo di Jacobi.

 

Queste proprietà permettono di calcolarlo in modo efficiente con un algoritmo analogo a quello di Euclide per il calcolo del massimo comun divisore.

Dato che può essere calcolato senza conoscere la scomposizione degli argomenti, fornisce un criterio efficiente per determinare se un numero n dispari è composto: si prende un intero a a caso, primo rispetto a n, e si calcolano Simbolo di Jacobi (a | n) e Formula derivata dal teorema di Eulero; se i due valori differiscono, n è composto, se sono uguali n è probabilmente primo (e si può ripetere l’esame con un differente valore di a).

La tabella seguente mostra i primi valori di Simbolo di Jacobi.

m \ n

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

2

1

0

–1

0

–1

0

1

0

1

0

–1

0

–1

0

1

0

1

0

–1

0

3

1

–1

0

1

–1

0

1

–1

0

1

–1

0

1

–1

0

1

–1

0

1

–1

4

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

5

1

–1

–1

1

0

1

–1

–1

1

0

1

–1

–1

1

0

1

–1

–1

1

0

6

1

0

0

0

1

0

1

0

0

0

1

0

–1

0

0

0

–1

0

–1

0

7

1

1

–1

1

–1

–1

0

1

1

–1

1

–1

–1

0

1

1

–1

1

–1

–1

8

1

0

–1

0

–1

0

1

0

1

0

–1

0

–1

0

1

0

1

0

–1

0

9

1

1

0

1

1

0

1

1

0

1

1

0

1

1

0

1

1

0

1

1

10

1

0

1

0

0

0

–1

0

1

0

–1

0

1

0

0

0

–1

0

–1

0

11

1

–1

1

1

1

–1

–1

–1

1

–1

0

1

–1

1

1

1

–1

–1

–1

1

12

1

0

0

0

–1

0

1

0

0

0

–1

0

1

0

0

0

–1

0

1

0

13

1

–1

1

1

–1

–1

–1

–1

1

1

–1

1

0

1

–1

1

1

–1

–1

–1

14

1

0

1

0

1

0

0

0

1

0

–1

0

1

0

1

0

–1

0

1

0

15

1

1

0

1

0

0

–1

1

0

0

–1

0

–1

–1

0

1

1

0

1

0

16

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

17

1

1

–1

1

–1

–1

–1

1

1

–1

–1

–1

1

–1

1

1

0

1

1

–1

18

1

0

0

0

–1

0

1

0

0

0

–1

0

–1

0

0

0

1

0

–1

0

19

1

–1

–1

1

1

1

1

–1

1

–1

1

–1

–1

–1

–1

1

1

–1

0

1

20

1

0

–1

0

0

0

–1

0

1

0

1

0

–1

0

0

0

–1

0

1

0

21

1

–1

0

1

1

0

0

–1

0

–1

–1

0

–1

0

0

1

1

0

–1

1

22

1

0

–1

0

–1

0

–1

0

1

0

0

0

1

0

1

0

–1

0

1

0

23

1

1

1

1

–1

1

–1

1

1

–1

–1

1

1

–1

–1

1

–1

1

–1

–1

24

1

0

0

0

1

0

1

0

0

0

1

0

–1

0

0

0

–1

0

–1

0

25

1

1

1

1

0

1

1

1

1

0

1

1

1

1

0

1

1

1

1

0

26

1

0

–1

0

1

0

–1

0

1

0

1

0

0

0

–1

0

1

0

1

0

27

1

–1

0

1

–1

0

1

–1

0

1

–1

0

1

–1

0

1

–1

0

1

–1

28

1

0

–1

0

–1

0

0

0

1

0

1

0

–1

0

1

0

–1

0

–1

0

29

1

–1

–1

1

1

1

1

–1

1

–1

–1

–1

1

–1

–1

1

–1

–1

–1

1

30

1

0

0

0

0

0

–1

0

0

0

1

0

1

0

0

0

1

0

–1

0

31

1

1

–1

1

1

–1

1

1

1

1

–1

–1

–1

1

–1

1

–1

1

1

1

32

1

0

–1

0

–1

0

1

0

1

0

–1

0

–1

0

1

0

1

0

–1

0

33

1

1

0

1

–1

0

–1

1

0

–1

0

0

–1

–1

0

1

1

0

–1

–1

34

1

0

1

0

1

0

–1

0

1

0

1

0

–1

0

1

0

0

0

–1

0

35

1

–1

1

1

0

–1

0

–1

1

0

1

1

1

0

0

1

1

–1

–1

0

36

1

0

0

0

1

0

1

0

0

0

1

0

1

0

0

0

1

0

1

0

37

1

–1

1

1

–1

–1

1

–1

1

1

1

1

–1

–1

–1

1

–1

–1

–1

–1

38

1

0

1

0

–1

0

1

0

1

0

–1

0

1

0

–1

0

1

0

0

0

39

1

1

0

1

1

0

–1

1

0

1

1

0

0

–1

0

1

–1

0

–1

1

40

1

0

1

0

0

0

–1

0

1

0

–1

0

1

0

0

0

–1

0

–1

0

41

1

1

–1

1

1

–1

–1

1

1

1

–1

–1

–1

–1

–1

1

–1

1

–1

1

42

1

0

0

0

–1

0

0

0

0

0

1

0

1

0

0

0

1

0

1

0

43

1

–1

–1

1

–1

1

–1

–1

1

1

1

–1

1

1

1

1

1

–1

–1

–1

44

1

0

1

0

1

0

–1

0

1

0

0

0

–1

0

1

0

–1

0

–1

0

45

1

–1

0

1

0

0

–1

–1

0

0

1

0

–1

1

0

1

–1

0

1

0

46

1

0

–1

0

1

0

–1

0

1

0

1

0

–1

0

–1

0

–1

0

1

0

47

1

1

1

1

–1

1

1

1

1

–1

–1

1

–1

1

–1

1

1

1

–1

–1

48

1

0

0

0

–1

0

1

0

0

0

–1

0

1

0

0

0

–1

0

1

0

49

1

1

1

1

1

1

0

1

1

1

1

1

1

0

1

1

1

1

1

1

50

1

0

–1

0

0

0

1

0

1

0

–1

0

–1

0

0

0

1

0

–1

0

51

1

–1

0

1

1

0

–1

–1

0

–1

1

0

1

1

0

1

0

0

1

1

52

1

0

1

0

–1

0

–1

0

1

0

–1

0

0

0

–1

0

1

0

–1

0

53

1

–1

–1

1

–1

1

1

–1

1

1

1

–1

1

–1

1

1

1

–1

–1

–1

54

1

0

0

0

1

0

1

0

0

0

1

0

–1

0

0

0

–1

0

–1

0

55

1

1

–1

1

0

–1

1

1

1

0

0

–1

1

1

0

1

1

1

–1

0

56

1

0

1

0

1

0

0

0

1

0

–1

0

1

0

1

0

–1

0

1

0

57

1

1

0

1

–1

0

1

1

0

–1

–1

0

–1

1

0

1

–1

0

0

–1

58

1

0

1

0

–1

0

1

0

1

0

1

0

–1

0

–1

0

–1

0

1

0

59

1

–1

1

1

1

–1

1

–1

1

–1

–1

1

–1

–1

1

1

1

–1

1

1

60

1

0

0

0

0

0

–1

0

0

0

–1

0

–1

0

0

0

1

0

1

0

61

1

–1

1

1

1

–1

–1

–1

1

–1

–1

1

1

1

1

1

–1

–1

1

1

62

1

0

1

0

–1

0

1

0

1

0

1

0

1

0

–1

0

–1

0

–1

0

63

1

1

0

1

–1

0

0

1

0

–1

1

0

–1

0

0

1

–1

0

–1

–1

64

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

65

1

1

–1

1

0

–1

1

1

1

0

–1

–1

0

1

0

1

–1

1

–1

0

66

1

0

0

0

1

0

–1

0

0

0

0

0

1

0

0

0

1

0

1

0

67

1

–1

–1

1

–1

1

–1

–1

1

1

–1

–1

–1

1

1

1

1

–1

1

–1

68

1

0

–1

0

–1

0

–1

0

1

0

–1

0

1

0

1

0

0

0

1

0

69

1

–1

0

1

1

0

–1

–1

0

–1

1

0

1

1

0

1

1

0

–1

1

70

1

0

–1

0

0

0

0

0

1

0

–1

0

–1

0

0

0

1

0

1

0

71

1

1

1

1

1

1

–1

1

1

1

–1

1

–1

–1

1

1

–1

1

1

1

72

1

0

0

0

–1

0

1

0

0

0

–1

0

–1

0

0

0

1

0

–1

0

73

1

1

1

1

–1

1

–1

1

1

–1

–1

1

–1

–1

–1

1

–1

1

1

–1

74

1

0

–1

0

1

0

1

0

1

0

–1

0

1

0

–1

0

–1

0

1

0

75

1

–1

0

1

0

0

1

–1

0

0

–1

0

1

–1

0

1

–1

0

1

0

76

1

0

–1

0

1

0

1

0

1

0

1

0

–1

0

–1

0

1

0

0

0

77

1

–1

–1

1

–1

1

0

–1

1

1

0

–1

1

0

1

1

1

–1

1

–1

78

1

0

0

0

–1

0

–1

0

0

0

–1

0

0

0

0

0

–1

0

1

0

79

1

1

–1

1

1

–1

–1

1

1

1

1

–1

1

–1

–1

1

–1

1

1

1

80

1

0

–1

0

0

0

–1

0

1

0

1

0

–1

0

0

0

–1

0

1

0

81

1

1

0

1

1

0

1

1

0

1

1

0

1

1

0

1

1

0

1

1

82

1

0

1

0

–1

0

–1

0

1

0

1

0

1

0

–1

0

–1

0

1

0

83

1

–1

1

1

–1

–1

1

–1

1

1

1

1

–1

–1

–1

1

1

–1

–1

–1

84

1

0

0

0

1

0

0

0

0

0

–1

0

–1

0

0

0

1

0

–1

0

85

1

–1

1

1

0

–1

1

–1

1

0

–1

1

–1

–1

0

1

0

–1

1

0

86

1

0

1

0

1

0

–1

0

1

0

–1

0

–1

0

1

0

1

0

1

0

87

1

1

0

1

–1

0

1

1

0

–1

1

0

1

1

0

1

1

0

–1

–1

88

1

0

–1

0

–1

0

–1

0

1

0

0

0

1

0

1

0

–1

0

1

0

89

1

1

–1

1

1

–1

–1

1

1

1

1

–1

–1

–1

–1

1

1

1

–1

1

90

1

0

0

0

0

0

–1

0

0

0

–1

0

1

0

0

0

–1

0

–1

0

91

1

–1

–1

1

1

1

0

–1

1

–1

–1

–1

0

0

–1

1

–1

–1

1

1

92

1

0

1

0

–1

0

–1

0

1

0

–1

0

1

0

–1

0

–1

0

–1

0

93

1

–1

0

1

–1

0

1

–1

0

1

1

0

–1

–1

0

1

1

0

1

–1

94

1

0

–1

0

1

0

1

0

1

0

1

0

1

0

–1

0

1

0

1

0

95

1

1

1

1

0

1

–1

1

1

0

1

1

1

–1

0

1

–1

1

0

0

96

1

0

0

0

1

0

1

0

0

0

1

0

–1

0

0

0

–1

0

–1

0

97

1

1

1

1

–1

1

–1

1

1

–1

1

1

–1

–1

–1

1

–1

1

–1

–1

98

1

0

–1

0

–1

0

0

0

1

0

–1

0

–1

0

1

0

1

0

–1

0

99

1

–1

0

1

1

0

–1

–1

0

–1

0

0

–1

1

0

1

–1

0

–1

1

100

1

0

1

0

0

0

1

0

1

0

1

0

1

0

0

0

1

0

1

0

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.