jacobiSymbol

Símbolo de Jacobi (a/n), generalização do símbolo de Legendre.

Categoria: Mathematics > Number Theory

Sintaxe

J = jacobiSymbol(a, n)

Descrição

O símbolo de Jacobi é o produto dos símbolos de Legendre sobre os fatores primos de n. Para n primo indica se a é resíduo quadrático: 1 se for, -1 se não for, 0 se n divide a. Para n composto, o valor 1 não garante que a seja um quadrado módulo n, mas -1 prova que não é.

O símbolo segue a reciprocidade quadrática, o que permite um cálculo rápido sem fatorar. Um n par gera erro.

Argumentos de entrada

a

Inteiro escalar ou array.

n

Inteiro ímpar positivo.

Argumentos de saída

J

0 se a e n têm fator comum; caso contrário 1 ou -1.

Exemplo

Resíduos módulo 7 e 15

jacobiSymbol(1:6, 7)
jacobiSymbol(7, 7)
jacobiSymbol(2, 15)

ans = 1×6

     1     1    -1     1    -1    -1
ans = 0
ans = 1

Veja também

isPrimitiveRoot eulerPhi mod isprime