S-3.8
(a) Mostre que se um número
não é divisível por 3 , então o resto da divisão de
por 3 é 1 .
(b) A partir desse dado, mostre que se um inteiro da forma
é múltiplo de 3 , então
e
são ambos múltiplos de 3 .
S-3.9 Mostre que se
, então o número
é composto.
(b) A partir desse dado, mostre que se um inteiro da forma
Passo 1
S-
trata de aritmética modular em módulo
: em (a) queremos mostrar que, se
, então o resto de
ao dividir por
é
; em (b) usar esse fato para concluir que, se
, então
e
. S-
pede para provar que, para
, o número
é composto, o que será feito por fatoração de polinômios.
Passo 2
(Prova de S-
a) Como
, temos duas possibilidades:
ou
.
Se , então
Se
logo o resto é
.
Se , então
Se
de novo resto
. Assim, se
então
.
Passo 3
(Prova de S-
b) Suponha
. Como cada quadrado módulo
só pode ser
(se o número for múltiplo de
) ou
(pelos casos acima), e só há duas escolhas de soma que dão
em
:
i.e.\
e
.
Passo 4
(S-
) Para mostrar que
é composto quando
, usamos a identidade de Sophie-Germain, que fatora expressões da forma
.
Passo 5
Aplicando com
e
, escrevemos
Para
, ambos fatores
, portanto
é produto de dois inteiros maiores que
, logo é composto.
Resposta
(a) Se
então
.
(b) Se então
e
.
S- :
é composto para
.
(b) Se
S-