Preparação para o Exame de Qualificação - PROFMAT Encontro 3: Teoria dos Números 1. Demonstre que se |a bc e ( , )mdc a b d= , então |a cd .

2. Se , e a m n são inteiros positivos e n é ímpar, prove que ( 1, 1) 2n mmdc a a− + ≤ .

3. Para todo inteiro n , prove que: 2( 1, 1) 1 ou 3mdc n n n− + + = .

4. Admitindo-se a Conjectura de Goldbach: “Todo inteiro par maior que 2 é a soma de dois números primos positivos”, prove que todo inteiro para maior que 5 é igual à soma de três primos positivos.

5. Determine infinitos inteiros n tais que 2 27n + é divisível por 7.

6. Determine o dígito das unidades de 777 .

7. Ache todos os inteiros estritamente positivos com a seguinte propriedade: fornecem resto 6 quando divididos por 11 e resto 3 quando divididos por 7. 8. Resolver o sistema:

1mod 22mod 33mod 5

xxx

≡ ≡ ≡

9. Ache o menor inteiro 2a > tal que: 2 | a , ( )3 | 1a + , ( )4 | 2a + e ( )5 | 3a + .

10. Determine os dois últimos dígitos de 10003 e de 100077 .

11. (Exame de Qualificação - PROFMAT) Um truque de adivinhação de números. (a) (5pts) Descreva e justifique métodos práticos para obter os restos da divisão por 9, 10 e 11, respectivamente, de um número natural escrito no sistema decimal. (b) (5pts) Ache as soluções mínimas de cada uma das seguintes congruências: i. 110 1mod9y ≡

ii. 99 1mod10y ≡

iii. 90 1mod11y ≡

(c) (10pts) Um mágico pede a sua audiência para escolher um número natural de pelo menos dois algarismos e menor do que 1000, e de lhe revelar apenas os restos 9 10 11, e r r r da divisão de M por 9, 10 e 11, respectivamente (tarefa fácil, pelo item (a)). Sem nenhuma

outra informação ele consegue descobrir. Explique como ele consegue fazer isto. (d) (5pts) Supondo que a plateia tenha dado as seguintes informações ao mágico: 9 10 117, =8 e 9r r r= = , qual foi o valor de M que o

mágico achou? 12. (Exame de Qualificação - PROFMAT) Considere o sistema de congruências:

1 1

2 2

x c mod nx c mod n≡≡

Denotamos como de costume o mdc e o mmc de 1 2en n por 1 2 1 2, e ( ) [ ],n n n n , respectivamente.

(a) Mostre que e 'a a são soluções do sistema se, e somente se, 1 2[ ]' , a a mod n n≡ . O enunciado, da forma como está, é incorreto. O

certo seria: Mostre que, se a é solução, então 'a é solução se, e somente se, 1 2[' ], a a mod n n≡ .

(b) Mostre que o sistema admite solução se, e somente se, 2 1 1 2( , ) c c mod n n≡ .

(c) Dadas as progressões aritméticas ( )na de primeiro termo 5 e razão 14 e ( )nb de primeiro termo 12 e razão 21, mostre que elas

possuem termos comuns (isto é, existem er s tais que r sa b= ). Mostre que esses termos comuns formam uma PA e determine seu

primeiro termo e sua razão.