Olimpíadas ⇒ (Banco IBERO) Teoria dos números

[Deleted User 23699]

Para cada natural n, definimos d(n) a quantidade de divisores de n e [tex3]\varphi (n)[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\varphi (n)[/tex3]

a quantidade de inteiros coprimos com n e menores do que ou iguais a n. Ache todos os inteiros positivos n, tais que [tex3]d(n)+\varphi (n)=n[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]d(n)+\varphi (n)=n[/tex3]

Resposta

---

8 ou 9

[leozitz]

Resposta

---

d(1) + \phi(1) = 2
d(2) + \phi(2) = 3
d(3) + \phi(3) = 2 + 2 = 4
d(4) + \phi(4) = 3 + 2 = 5
eita, que estranho. parece q aquilo é sempre n + 1
d(5) + \phi(5) = 2 + 4 = 6
d(6) + \phi(6) = 3 + 2 = 5
d(7) + \phi(7) = 2 + 6 =
d(8) + \phi(8) = 4 + 4 = 8
d(9) + \phi(9) = 9
d(10) + \phi(10) = 4 + 4 = 8

note o seguinte, se p for primo d(p) + \phi(p) = p + 1
outra coisa interessante é que d(n) e phi(n) tem algo em comum em sua definição, o que importa é mais o menos os fatores do numero e outros números que tem esses fatores.

defina [tex3]A = \{a: (a, n) > 1\ e \ a \le n \}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]A = \{a: (a, n) > 1\ e \ a \le n \}[/tex3]

[tex3]\phi(n) = n - x[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\phi(n) = n - x[/tex3]

onde [tex3]x = |A|[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]x = |A|[/tex3]

, ou seja, phi(n) = qtd de números de 1 até n, inclusive, relativamente primos com n, depois de retirar esses números sobra exatamente os números com fatores em comum, sendo assim queremos encontrar todo n tal que
[tex3]d(n) = x[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]d(n) = x[/tex3]

mas se você notar, o conjunto A contem todo divisor de n, logo precisamos encontrar todo n tal que [tex3](a, n) > 1 \ e \ a \le n\implies a|n[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3](a, n) > 1 \ e \ a \le n\implies a|n[/tex3]

se n for composto, e não for potencia de primos então não funciona, [tex3]n = p^kb[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n = p^kb[/tex3]

onde (p, b) = 1 e k é um inteiro positivo, por hipótese b > 1, e seja p o menor primo que divide n. então p^{k+1} nos dá essa contradição já q é menor q n (pois b > p já que p é minimo) e o mdc é p^k > 1.

logo n é primo ou potencia de primo. ai agora, me parece uma boa ideia voltar as nossas funções pq elas são bem tranquilas para calcular em potencias de primos
[tex3]d(p^k) = k+1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]d(p^k) = k+1[/tex3]

e [tex3]\phi(p^k) = (p-1)p^{k-1}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\phi(p^k) = (p-1)p^{k-1}[/tex3]

[tex3]k + 1 + (p-1)p^{k-1} = p^k[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]k + 1 + (p-1)p^{k-1} = p^k[/tex3]

[tex3]k + 1 + p^k - p^{k-1} = p^k[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]k + 1 + p^k - p^{k-1} = p^k[/tex3]

[tex3]k + 1 = p^{k-1}\ge 2^{k-1}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]k + 1 = p^{k-1}\ge 2^{k-1}[/tex3]

ai agora fica tranquilo restringir k com indução e depois é só testar