raiz primitiva módulo n

Na aritmética modular, um ramo da teoria dos números, um número é uma raiz primitiva módulo n se todo número coprimo a for congruente com uma potência de módulo . Ou seja, é uma raiz primitiva módulo se para cada inteiro coprimo com , existe um inteiro tal que . Esse valor é chamado de índice ou logaritmo discreto de para a base módulo . Observe que é uma raiz primitiva do módulo se e somente se é um gerador do grupo multiplicativo de inteiros módulo n. Gauss definiu raízes primitivas no Artigo 57 do Disquisitiones Arithmeticae (1801), onde ele atribuiu a Euler a cunhagem do termo. No Artigo 56, ele afirmou que Lambert e Euler sabiam deles, mas ele foi o primeiro a demonstrar rigorosamente que raízes primitivas existem para um primo. Na verdade, o Disquisitiones contém duas provas: a do Artigo 54 é uma prova de existência não construtiva, enquanto a outra do Artigo 55 é construtiva.