### 6.7.29 Symbole de Legendre : `legendre_symbol`

Lorsque n est premier, on définit le symbole de Legendre de a noté (a/n) par :

⎛
⎜
⎜
⎝

a
n

⎞
⎟
⎟
⎠

=

⎧
⎪
⎨
⎪
⎩

0 | si a=0 modn
1 | si a ≠ 0 modn et si a=b2 modn
−1 | si a ≠ 0 modn et si a ≠ b2 modn

Quelques propriétés

- Si n est premier :

  a

  n−1
  2

  =

  ⎛
  ⎜
  ⎜
  ⎝

  a
  n

  ⎞
  ⎟
  ⎟
  ⎠

  modn

- ⎛
  ⎜
  ⎜
  ⎝

  p
  q

  ⎞
  ⎟
  ⎟
  ⎠

  .

  ⎛
  ⎜
  ⎜
  ⎝

  q
  p

  ⎞
  ⎟
  ⎟
  ⎠

  =

  (−1)

  p−1
  2

  .(−1)

  q−1
  2

  si p et q sont impairs et positifs

  ⎛
  ⎜
  ⎜
  ⎝

  2
  p

  ⎞
  ⎟
  ⎟
  ⎠

  =

  (−1)

  p2−1
  8

  ⎛
  ⎜
  ⎜
  ⎝

  −1
  p

  ⎞
  ⎟
  ⎟
  ⎠

  =

  (−1)

  p−1
  2

`legendre_symbol` a deux paramètres a et n et renvoie le symbole de Legendre (a/n).
On tape :

`legendre_symbol(26,17)`

On obtient :

`1`

On tape :

`legendre_symbol(27,17)`

On obtient :

`-1`

On tape :

`legendre_symbol(34,17)`

On obtient :

`0`