Congruência - Exercícios - Avançado
(01) Prove que para todo inteiro n:
a ) n 3 − n é divisível por 3.
b) n 5 − n é divisível por 5.
c) n 7 − n é divisível por 7.
d ) n 31 − n é divisível por 31.
e) n 101 − n é divisível por 101.
(02) Prove que:
a ) 3 6 n − 2 6 n é divisível por 35, ∀ n ∈ Z.
b) n 5 − 5n 3 + 4n é divisível por 120, ∀ n ∈ Z.
(
)(
)
(03) Demonstre que n 2 n 2 − 1 n 2 − 4 ≡ 0 (mod .360 ) .
9
(04) Determine os dois últimos algarismos de 9 9 .
Resposta: 89
(05) Prove que n 2 + 3n + 5 é divisível por 121, ∀ n ∈ Z.
(06) Prove que 2222 5555 + 5555 2222 é divisível por 7.
(07) Mostre que a equação x 2 − 7 y 2 = 3 , não possui solução em Z.
Solução:
x 2 − 7 y 2 ≡ x 2 ( mod . 7 )
Porém
⎧x
⎪x
⎪
⎪x
⎪
⎨x
⎪x
⎪
⎪x
⎪
⎩x
⎧x 2 ≡ 0 (mod .7)
≡ 0 (mod .7)
⎪ 2
⎪x ≡ 1 (mod .7)
≡ 1 (mod .7)
⎪ 2
⎪x ≡ 4 (mod .7)
≡ 2 (mod .7)
⎪
≡ 3 (mod .7) ⇒ ⎨x 2 ≡ 2 (mod .7) ⇒ S = { }.
⎪ 2
≡ 4 (mod .7)
⎪x ≡ 2 (mod .7)
≡ 5 (mod .7)
⎪x 2 ≡ 4 (mod .7)
⎪
≡ 6 (mod .7)
⎪x 2 ≡ 1 (mod .7)
⎩
(08) (OBM - Banco) Mostre que a equação 15x 2 − 7 y 2 = 9 , não possui solução em Z.
(09) (OBM - Banco) Sejam x , y, z ∈ Z tais que x 3 + y 3 − z 3 é múltiplo de 7. Prove que um desses números é múltiplo
de 7.
Solução:
⎧n 3 ≡ 0 (mod .7)
⎪ 3
⎪n ≡ 1 (mod .7)
⎪ 3
⎪n ≡ 1 (mod .7)
≡ 2 (mod .7)
⎪
≡ 3 (mod .7) ⇒ ⎨n 3 ≡ − 1 (mod .7)
⎪ 3
≡ 4 (mod .7)
⎪n ≡ 1 (mod .7)
≡ 5 (mod .7)
⎪n 3 ≡ − 1 (mod .7)
⎪
≡ 6 (mod .7)
⎪n 3 ≡ − 1 (mod .7)
⎩
Suponha que x , y e z não múltiplos de 7,
⎧n
⎪n
⎪
⎪n
⎪
⎨n
⎪n
⎪
⎪n
⎪
⎩n
≡ 0 (mod .7)
≡ 1 (mod .7)
⎧x 3
⎪ 3
⎪x
⎧x 3 + y 3 ≡ − 2 (mod .7)
⎪ 3
⎪⎪ 3
⎪x
3
⇒ ⎨x + y ≡ 0 (mod .7) ⇒ ⎨
3
⎪ 3
⎪x
3
x
y
2
(mod
.
7
)
+
≡
⎪⎩
⎪ 3
⎪x
⎪x 3
⎩
+ y 3 − z 3 ≡ − 1 (mod .7)
+ y 3 − z 3 ≡ − 3 (mod .7)
+ y 3 − z 3 ≡ 1 (mod .7)
+ y 3 − z 3 ≡ − 1 (mod .7)
⇒ x 3 + y3 − z
3
não é múltiplo de 7 .
+ y 3 − z 3 ≡ 3 (mod .7)
+ y 3 − z 3 ≡ 1 (mod .7)
(10) (OBM - Banco) Sejam x , y, z ∈ Z tais que x 2 + y 2 = z 2 . Prove que ou x e y são ímpares ou x y é múltiplo de 6.
(11) (OBM - Banco) Mostre que 3 não divide 1 + 4 n , n ∈ IN.
Solução:
4 ≡ 1 ( mod .3 ) ⇒ 4 n ≡ 1 ( mod .3 ) , n ∈ IN ⇒
4 n + 1 ≡ 2 ( mod .3 ).
(12) (OBM - Banco) Mostre que: 2 n = 1 (mod .7) ⇔ n ≡ 0 (mod .3)
(13) (OIM)
(a) Determine todos os inteiros positivos tais que 2 n − 1 é divisível por 7.
(b) Prove que não existe inteiro positivo para o qual 2 n + 1 seja divisível por 7.
Resposta:
a ) n ≡ 0 (mod .3)
(14) Prove que:
m.d.c(p, q ) = 1 ⇒ p q −1 + q p −1 ≡ 1 (mod .pq ), p, q ∈ IN.
(15) Sejam p ∈ IN, primo e a , b ∈ Z , tais que não são divisíveis por p, prove que:
a ) a p ≡ b p (mod .p ) ⇒ a ≡ b (mod .p ).
(
)
b) a p ≡ b p (mod .p ) ⇒ a p ≡ b p mod .p 2 .
(16) Seja p∈ IN, primo , prove que:
p −1
a)
∑k
p −1
∑k
p
k =1
p −1
b)
≡ − 1 (mod .p ).
≡ 0 (mod .p ).
k =1
(17) (OBM - Banco) Seja
quadrados perfeitos.
A = 4 n ( 8m + 7 ) , n , m ∈ Z + . Prove que A não pode ser escrito como a soma de três
(18) (OBM) Seja k um inteiro positivo tal que k (k + 1) 3 é um quadrado perfeito. Prove que k 3 e (k + 1) são quadrados
perfeitos.
(19) (OBM) Mostre que existe um numero da forma 1999
...9991
142
43 , que é múltiplo de 1991.
n noves , n > 2
(20) (OIM) Sejam m, n ∈ IN, 1 ≤ m < n , tais que os três últimos algarismos de 1978 m são iguais aos de 1978 n .
Determine m e n tais que m + n é mínimo.
Resposta:
n + m = 106, n = 103 e m = 3.