Re: [obm-l] Alguns problemas de Teoria de Numeros

On 12/14/05, Aldo Munhoz <amunhoz@gmail.com > wrote:

Eu não entendi porque você quebrou o primeiro em soma de seus componentes. Por que isso?

Bruno França dos Reis wrote:
1) 723548923452346857398473659 mod 9 = 72 + 3 + 54 + 8 + 9 + 23 + 45 + 23 + 468 + 5 + 7 + 3 + 9 + 847 + 36 + 5 + 9 mod 9 = 3 + 8 + 23 + 23 + 5 + 7 + 3 + 847 + 5 mod 9 = 2 + 1 + 3 + 3 + 1 + 5 mod 9 = 15 mod 9 = 6

2) n^7 - n = (n^6 - 1)n = (n^3 + 1)(n^3-1)n

É fácil ver que isso é sempre um número par, pois se n o for, acabou. Se não, n não será, bem como n^3, e então n^3+-1 será.
Tomando a expressão mod 3, temos 3 casos:
n = 0 mod 3:
Então a expressão é divisível por 3
n = 1 mod 3:
n^3 - 1 = 1^3 - 1 = 0 mod 3
Então novamente a expressão é div. por 3
n = -1 mod 3:
n^3 + 1 = (-1)
Logo a expr. é div por 3 sempre.
Agora mod 7:
n = 0 mod 7, trivial
n = +-1 mod 7 ==> n^3 -+1 = 0 mod 7
n = +-2 mod 7 ==> n^3 -+ 1 = 0 mod 7
n = +-3 mod 7 ==> n^3 +- 1 = 0 mod 7
Logo o número n^7 - n é sempre divisível por 2, 3, e 7. Logo é sempre múltiplo de 42.

3) 13^143 + 6^15 mod 7 = (-1)^143 + (-1)^15 = -2 = 5 mod 7.
(-2)^33 = (-2)^(11*3) = ((-2)^3)^11 = (-8)^11 = -1 = 6 mod 7.
Portanto o resto da divisão é 6.

4) Esse aqui braçal a resolução, é só armar a multiplicação e ir fazendo conta. Dá 153846: 4 * 153846 = 615384

5) a) 7 | 2^n - 1, n = ?
Quero 2^n - 1 = 0 mod 7 <==> 2^n = 1 mod 7
Tomando n < 3 nenhum satisfaz (0 satisfaz, mas 0 é natural? depende da convenção). Tomemos então n = 3. Satisfaz. Se n > 3, podemos escrever k = n-3, e então
2^n = 2^k * 2^3 = 2^k * 1 = 2^k mod 7.
Vemos k < 3 não satisfaz (0 satisfaz, blablabla). Tomando k = 3, satisfaz. Vemos então que todos os números multiplos de 3 satisfazem, e apenas estes.
2^3a = (2^3)^a = 1^a = 1 mod 7
2^(3a+1) = 2 mod 7
2^(3a+2) = 4 mod 7

b) Temos então que
(i) n = 3a ==> 2^n mod 7 =1 ==> 2^n + 1 mod 7 = 2
(ii) n = 3a+1 ==> 2^n mod 7 = 2 ==> 2^n + 1 mod 7 = 3
(ii) n = 3a+2 ==> 2^n mod 7 =4 ==> 2^n + 1 mod 7 = 5
o que mostra que nunca será 2^n + 1 múltiplo de 7.

Vou almoçar, depois brinco com os outros.

Abraço,
Bruno

On 12/14/05, Aldo Munhoz <amunhoz@gmail.com > wrote:
Pessoal,

Segue alguns problemas de Teoria de Números.

1. Determine o resto da divisão de 723548923452346857398473659 por 9.

2. Mostra que para qualquer n, o número n^7 - n é múltiplo de 42.

3. Determina o resto da divisão de (13^143 + 6^15)^33 por 7.

4. (OIM-1962) Encontre o menor número natural n tal que:
(a) o algarismo das unidades é 6;
(b) se apagarmos esse 6 e o pusermos antes dos outros dígitos, o novo número é o quádruplo do número original.

5. (OIM-1964)
(a) Encontra todos os inteiros positivos n tais que 2^n - 1 é múltiplo de 7.
(b) Mostra que não há nenhum inteiro positivo n para o qual 2^n + 1 é divisível por 7.

6. Um cesto tem capacidade para 300 ovos mas não está totalmente cheio. Se retirarmos os ovos 2 de cada vez, no final sobra 1; se forem 3 de cada vez, sobram 2; se forem 4 de cada vez, sobram 3; se forem 5 de cada vez, sobram 4; se forem 6 de cada vez, sobram 5; se forem 7 de cada vez, o cesto fica vazio. Quantos ovos estão no cesto?

7. Determina um número inteiro cujos restos na divisão por 3, 5 e 7 são respectivamente 2, 3 e 2.

8. Mostra que todo o inteiro da forma 3k + 2 tem um factor primo da mesma forma.

9. Mostra que todo o número primo da forma 3k + 1 é da forma 6t + 1.

10. Indica quantos números de 4 algarismos, com os últimos três iguais, são divisíveis por 8.

11. Mostra que o algarismo das unidades de n, n2, n3, : : :, se repetem de 4 em 4.

========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================

--
Bruno França dos Reis
email: bfreis - gmail.com
gpg-key: http://planeta.terra.com.br/informatica/brunoreis/brunoreis.key
icq: 12626000

e^(pi*i)+1=0
========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================