Question

(Aritmética: Números primos – congruência modular – aritmética dos restos)

Sejam p₁, p₂ números naturais primos. Mostre que existe $r\in\{1,\,2,\,\ldots,\,p-1\}$ tal que

$p_2\not\equiv r\pmod{p_1}$

para todo p₂ < p₁.

─────

O símbolo ≢ significa "não é congruente a".

Answer 1

Correção do enunciado:

Sejam p₁, p₂ números naturais primos. Mostre que existe $r \in \{1,\:2,\:\dots,\:p_1-1\}$ tal que

$p_2 \not\equiv r \pmod {p_1}$

Para todo p₂ < p₁.

────────────────────

Com o intervalo de r que foi dado, é evidente que não pode ser adicionado ou subtraído a r algum múltiplo de p₁. Desse modo, p₂ somente pode ser congruente a si mesmo, mod p₁. E como r contém "1", e 1 não é primo, logo:

$p_2 \not\equiv 1 \pmod {p_1}$

Para qualquer p₂, demonstrando o solicitado.