Soluções problemas da semana 8

Iniciante: Seja $S$ o menor conjunto de inteiros positivos tal que:

a) $2$ está em $S$

b) Se $n^2$ está em $S$, $n$ está em $S$

c) Se $n$ está em $S$, $(n + 5)^2$ está em $S$

Quais inteiros positivos não estão em $S$?

(Escrito por Luca Zanardi)

Conhecimentos Prévios Necessários:

• Congruência Modular

Primeiramente, note que, se $n$ está em $S, (n+5)^2$ está em $S$, e assim, $n+5$ também estará obrigatoriamente. Dessa forma, é fácil ver que, se $n$ está em $S, 5k+n$ também estará em $S$, para todo $k$ inteiro não negativo. Como $2$ está em $S$, todo número inteiro positivo congruente a $2 \pmod{5}$ também está.

Agora, perceba que $(2+5)^2 = 49$ está em $S$, e $X = (49+5)^2 \equiv (-1)^2 \equiv 1 \pmod{5}$ está em $S$, portanto, todo número maior que $X$ congruente a $1$ está em $S$. Em particular, os números $3^{(2^n)}, 4^{(2^n)}, 6^{(2^n)}$ também estão, para algum $n$ suficientemente grande, logo, $3, 4, 6$ também estão. Assim sabemos que todo número congruente a $1, 2, 3, 4 \pmod{5}$ maior que $1$ está em $S$. Com isso, veja que $S = \{ x | x > 1, 5 \nmid x \}$ é um conjunto válido. Portanto, nossa resposta é $1$ e todos os números divisíveis por 5.

INTERMEDIÁRIO: Determine todos os pares de inteiros positivos $(a,b)$ tais que $a \mid b \mid a^2 \mid b^3 \mid a^4 \mid b^5 \mid \cdots$

(Escrito por João Gilberti)

Conhecimentos Prévios Necessários:

• Expoentes em Primos
• Teorema do Sanduíche

Temos que, $\forall k \in \mathbb{N}$, temos que $a^{2k} \mid b^{2k+1} \mid a^{2k+2}$, portanto, tome $p$ um primo qualquer,

$\nu_p(a^{2k}) \le \nu_p (b^{2k+1}) \le \nu_p (a^{2k+2}) \Longrightarrow 2k \nu_p(a) \le (2k+1) \nu_p(b) \le (2k+2) \nu_p(a)$ $\Longrightarrow \frac{2k}{2k+1} \le \frac{\nu_p(b)}{\nu_p(a)} \le \frac{2k+2}{2k+1}$

Para todo $k \in \mathbb{N}$, então, veja que $\lim_{k \rightarrow \infty} \frac{2k}{2k+1} = \lim_{k \rightarrow \infty} 1 - \frac{1}{2k+1} = 1$, e que $\lim_{k \rightarrow \infty} \frac{2k+2}{2k+1} = \lim_{k \rightarrow \infty} 1 + \frac{1}{2k+1} = 1$, logo, pelo teorema do sanduíche, temos que

$\lim_{k \rightarrow \infty} \frac{2k}{2k+1} \le \lim_{k \rightarrow \infty} \frac{\nu_p(b)}{\nu_p(a)} \le \lim_{k \rightarrow \infty} \frac{2k+2}{2k+1} \Longrightarrow 1 \le \frac{\nu_p(b)}{\nu_p(a)}\le 1 \Longrightarrow \nu_p(b) = \nu_p(a)$

Para todo primo $p$, ou seja, a fatoração em primos de $a, b$ são as mesmas, então, $a = b$.

AVANÇADO: Seja $p_i$ com $i = 1, 2, \cdots , k$ a sequência dos números primos (Por exemplo, $p_1 = 2, p_2 = 3, p_3 = 5 \cdots$). Seja $N = p_1 p_2 \cdots p_k$. Prove que no conjunto $\{ 1, 2, \cdots , n \}$ existem exatamente $\frac{N}{2}$ números que são divisíveis por uma quantidade impar de $p_i$.

(Escrita por Leonardo do Carmo)

Solução