[skip-to-content]

Seção 1.2 Aula 02 - Divisibilidade II

Definição 1.2.1.

Dados dois inteiros \(a\) e \(b\text{,}\) com \(a \neq 0\text{,}\) dizemos que \(a\) divide \(b\) ou que \(a\) é um divisor de \(b\) ou ainda que \(b\) é um múltiplo de \(a\) e escrevemos \(a|b\) se o \(r\) obtido pelo algoritmo de divisão aplicado à \(a\) e \(b\) é \(0\text{,}\) ou seja, se \(b = aq\) para algum inteiro \(q\text{.}\)

Exemplo 1.2.3.

(Olimpíada de Maio 2006). Encontre todos os naturais \(a\) e \(b\) tais que \(a|(b + 1)\) e \(b|(a + 1)\text{.}\)

Solução

Pelo Lema 1.2.2 ("Limitação"),

\begin{align*} a|(b+1) \amp\Rightarrow a\leq b+1\\ b|(a+1) \amp\Rightarrow b\leq a+1 \Leftrightarrow b-1\leq a \end{align*}

Ou seja,

\begin{equation*} b-1\leq a\leq b+1, \end{equation*}

então temos três possibilidades: \(a=b-1\) ou \(a=b\) ou \(a=b+1\text{.}\)

\(\bullet\) Se \(a=b-1\text{,}\) então

\begin{equation*} a|(b-1)\quad \text{e}\quad a|(b+1). \end{equation*}

Pelo item i do Lema 1.2.2, escolhendo \(x=-1\) e \(y=1\) temos

\begin{align*} a|\amp[(b-1)\cdot(-1) + (b+1)\cdot(1)]\\ a|\amp 2. \end{align*}

Então, \(a=1\) ou \(a=2\text{.}\) Se \(a=1, b=2\) e se \(a=2, b=3\text{.}\)

\(\bullet\) Se \(a=b\text{,}\) então

\begin{equation*} a|a\quad \text{e}\quad a|(a+1), \end{equation*}

Logo, \(a|[(a+1)-a].\) Portanto, \(a|1\) e consequentemente \(a=1\) e \(b=1\text{.}\)

\(\bullet\) Se \(a=b+1\text{,}\) isto significa que \(b=a-1\text{.}\) Assim,

\begin{equation*} b|(a-1)\quad \text{e}\quad b|(a+1), \end{equation*}

logo

\begin{equation*} b|(a+1)-(a-1). \end{equation*}

Portanto, \(b|2\text{,}\) então \(b=1, a=2\) ou \(b=2, a=3\text{.}\)

O conjunto de todas as soluções: \(\{(1,2),(2,3), (1,1), (2,1), (3,2)\}\)

Podemos escrever \(n\) da seguinte maneira:

\begin{align*} n =\amp~ 10\cdot r_kr_{k-1}\ldots r_1 + r_0\\ =\amp~ 2\cdot 5\cdot r_kr_{k-1}\ldots r_1 + r_0. \end{align*}

Assim,

\begin{equation*} r_0 = n- 2\cdot 5\cdot r_kr_{k-1}\ldots r_1, \end{equation*}

logo, \(2|n\) se, e somente se, \(2|r_0\text{.}\)

Podemos escrever \(n\) da seguinte maneira:

\begin{align*} n =\amp~ 100\cdot r_kr_{k-1}\ldots r_2 + r_1r_0\\ =\amp~ 4\cdot 25\cdot r_kr_{k-1}\ldots r_2 + r_1r_0. \end{align*}

Assim,

\begin{equation*} r_1r_0 = n - 4\cdot 25\cdot r_kr_{k-1}\ldots r_2, \end{equation*}

logo, \(4|n\) se, e somente se, \(4|r_1r_0\text{.}\)

\begin{equation*} n = r_k\cdot 10^k + r_{k-1}\cdot 10^{k-1}+\cdots+r_1\cdot 10 + r_0. \end{equation*}

Portanto,

\begin{align*} n -(r_k+\cdots+r_1+r_0)=\amp~ (r_k\cdot 10^k -r_k)+\cdots+(r_1\cdot 10-r_1) + r_0-r_0\\ =\amp~r_k\cdot \underbrace{(10^k-1)}_{9|} + \cdots+r_1\cdot \underbrace{(10-1)}_{9|} + 0, \end{align*}

ou seja,

\begin{equation*} n = r_k\cdot \underbrace{(10^k-1)}_{9|} + \cdots+r_1\cdot \underbrace{(10-1)}_{9|}+(r_k+\cdots+r_1+r_0). \end{equation*}

Então,

  1. \(3|n\) se, e somente se, \(3|(r_k+\cdots+r_1+r_0)\text{.}\)
  2. \(9|n\) se, e somente se, \(9|(r_k+\cdots+r_1+r_0)\text{.}\)

Se nosso número original está escrito na forma \(10a+b\text{,}\) então o número obtido após a operação descrita é \(a-2b\text{.}\) Basta mostrar que se \(7|a-2b\text{,}\) então \(7|10a+b\text{.}\)

Se \(7|a-2b\text{,}\) \(7|10\cdot(a-2b)\text{,}\) ou seja,

\begin{equation*} 7|10a-20b. \end{equation*}

Como \(7|21b\text{,}\) pela propriedade i. do Lema 1.2.2, concluímos que

\begin{equation*} 7|(10a-20b)\cdot 1 +(21b)\cdot 1, \end{equation*}

ou seja,

\begin{equation*} 7|10a+b\text{.} \end{equation*}
Exemplo 1.2.8.

Mostre que se \(7|3a+2b\text{,}\) então \(7|4a-2b\text{.}\)

Solução
\begin{equation*} 7|3a+2b \quad \text{e}\quad 7|7a\text{.} \end{equation*}

Pela propriedade i. do Lema 1.2.2,

\begin{equation*} 7|(7a)\cdot 1 + (3a+2b)\cdot(-1)\text{,} \end{equation*}

ou seja,

\begin{equation*} 7|4a-2b. \end{equation*}
Exemplo 1.2.9.

Usando os dígitos \(1,2,3,4,5,6,7\text{,}\) construímos vários números de sete dígitos distintos. Existem dois deles, distintos, tais que um divide o outro?

Solução

Suponha, por absurdo, que \(n_1 \lt n_2\) sejam dois desses números, com \(n_1|n_2\text{.}\) Vamos usar o critério de divisibilidade por \(9\text{.}\) Note que \(n_1\) e \(n_2\) possuem a mesma soma dos dígitos:

\begin{equation*} 1+2+3+4+5+6+7=28=9\cdot3+1\text{,} \end{equation*}

consequentemente \(9|n_1-1\) e \(9|n_2-1\text{.}\) Portanto,

\begin{equation*} n_1|n_2 - n_1\quad \text{e} \quad 9 | n_2 - n_1. \end{equation*}

Assim, existem \(A\) e \(B\) inteiros, tais que \(n_2-n_1 = n_1\cdot A = 9\cdot B\text{.}\) Logo, \(9|n_1\cdot A\) e como \(9\nmid n_1\text{,}\) concluímos que \(9|A\text{.}\) Portanto,

\begin{equation*} 9n_1|n_1 A \Rightarrow 9n_1|n_2-n_1\text{.} \end{equation*}

Pelo item ii. do Lema 1.2.2,

\begin{equation*} 9n_1\leq n_2-n_1 \Rightarrow 10n_1\leq n_2\text{.} \end{equation*}

Assim, \(n_2\) possui um dígito a mais que \(n_1\text{,}\) mas isto é um absurdo. Portanto, não existem dois números distintos usando os dígitos \(1,2,3,4,5,6,7\text{,}\) tais que um divide o outro.

Exemplo 1.2.10. (AIME 1986).

Qual é o maior inteiro \(n\) para o qual \(n^3+100\) é divisível por \(n+10\text{?}\)

Solução

Fazendo a divisão de \(n^3+100\) por \(n+10\text{,}\) obtemos:

\begin{equation*} n^3+100 = (n+10)(n^2-10n+100)-900 \end{equation*}

para que \((n+10)\) divida \((n^3+100)\) basta que \((n+10)|900\text{.}\) O maior \(n\) que satisfaz a condição é \(n=890\text{.}\)

Exemplo 1.2.11. (Leningrado 1989).

Seja \(A\) um número natural maior que \(1\text{,}\) e seja \(B\) um número natural que é um divisor de \(A^2+1\text{.}\) Prove que se \(B-A>0\text{,}\) então \(B-A>\sqrt{A}\text{.}\)

Solução
  1. Se \(B\) é um divisor de \(A^2+1\text{,}\) então \(B|A^2+1\text{.}\)
  2. Se \(B-A>0\text{,}\) então \(B-A=d\text{,}\) com \(d\in \mathbb{N}\text{.}\)

Então, \(B=A+d\) e pelo item a. vale

\begin{equation} A+d|A^2+1\text{.}\label{exem-lenin89_01}\tag{1.2.1} \end{equation}

Como \(A^2-d^2 = (A+d)(A-d)\text{,}\) temos

\begin{equation} A+d|A^2-d^2\text{.}\label{exem-lenin89_02}\tag{1.2.2} \end{equation}

Pelo item i. do Lema 1.2.2, usando (1.2.1) e (1.2.2), temos

\begin{equation*} A+d|(A^2+1)-(A^2-d^2), \end{equation*}

ou seja,

\begin{equation*} A+d|d^2+1. \end{equation*}

Pelo item ii. do Lema 1.2.2,

\begin{equation*} A+d\leq d^2+1\text{.} \end{equation*}

Se \(d=1\text{,}\) \(A=1\text{,}\) mas por hipótese \(A>1\text{.}\)

Se \(d>1\text{,}\) então

\begin{equation*} A\leq d^2\underbrace{-d+1}_{\leq -1}\lt d^2\text{.} \end{equation*}

Portanto,

\begin{equation*} (B-A)^2=d^2>A \Rightarrow B-A>\sqrt{A}. \end{equation*}
Exemplo 1.2.12.

(Extraído de [5.2]). Encontre todos os inteiros positivos \(n\) tais que \(2n^2+1|n^3+9n-17\text{.}\)

Solução

Como \(2n^2+1|2n^2+1\text{,}\) usando o item i. do Lema 1.2.2

\begin{align*} 2n^2+1|\amp(n^3+9n-17)\cdot 2+(2n^2+1)\cdot(-n)\\ 2n^2+1|\amp2n^3+18n-34-2n^3-n\\ 2n^2+1|\amp17n-34\\ 2n^2+1|\amp17(n-2). \end{align*}

Pelo item ii. do Lema 1.2.2, ou \(17(n-2)=0 \Rightarrow n=2\text{,}\) ou

\begin{equation*} |2n^2+1|\leq|17(n-2)|. \end{equation*}

Como a função no lado esquerdo da desigualdade é quadrática (dentro do módulo) e a função do lado direito é linear (dentro do módulo), precisamos testar apenas alguns valores para \(n\text{,}\) pois a partir de um determinado valor, a função quadrática sempre assume valores maiores que a linear.

\begin{align*} n=1:\amp~ 3\leq -7 (F)\\ n=3:\amp~ 19\leq 17 (F)\\ n=4:\amp~ 33\leq 34 (V)\\ n=5:\amp~ 51\leq 51 (V)\\ n=6:\amp~ 73\leq 68 (F) \end{align*}

Agora, precisamos testar se \(2n^2+1|n^3+9n-17\) para \(n=4\) e \(n=5\text{.}\)

\begin{align*} n=4:\amp~ 33|83 (F)\\ n=5:\amp~ 51|153 (V) \end{align*}

Portanto, todas as soluções são \(2\) e \(5\text{.}\)

Exemplo 1.2.13. (Leningrado 1990).

Sejam \(a\) e \(b\) números naturais tais que \(b^2+ba+1\) divide \(a^2+ab+1\text{.}\) Prove que \(a=b\text{.}\)

Solução

Por hipótese,

\begin{equation*} b^2+ba+1|a^2+ab+1. \end{equation*}

Pelo item ii. do Lema 1.2.2,

\begin{equation*} b^2+ba+1\leq a^2+ab+1 \Rightarrow b^2\leq a^2 \Rightarrow b\leq a. \end{equation*}

Como \(b^2+ba+1\) divide ele mesmo, podemos usar o item i. do Lema 1.2.2 para escrever:

\begin{align*} b^2+ba+1|\amp (a^2+ab+1)\cdot b+(b^2+ba+1)\cdot (-a)\\ b^2+ba+1|\amp a^2b+ab^2+b-ab^2-a^2b-a, \end{align*}

simplificando, ficamos com

\begin{equation*} b^2+ba+1|b-a \Rightarrow b^2+ba+1\leq |b-a|. \end{equation*}

Como \(b\leq a\text{,}\) \(|b-a| = a-b\text{.}\) Temos dois casos para analisar.

Caso 1: \(a-b\neq 0\text{,}\) então

\begin{align*} b^2+ba+1\leq\amp~ a-b\\ b^2+b+1\leq\amp~ a-ba\\ b^2+b+1\leq\amp~ a\underbrace{(1-b)}_{\leq0}. \end{align*}

Chegamos em um absurdo.

Caso 2: \(a=b\text{.}\) Então, \(b^2+ba+1=a^2+ab+1\text{.}\)

Exercícios 1.2.1 Exercícios

1.

Mostre que se \(3|a+7b\text{,}\) então \(3|a+b\text{.}\)

2.

Mostre que se \(7|a+3b\text{,}\) então \(7|13a+11b\text{.}\)

3.

Mostre que se \(19|3x+7y\text{,}\) então \(19|43x+75y\text{.}\)

4.

Mostre que se \(17|3a+2b\text{,}\) então \(17|10a+b\text{.}\)

5.

O número de seis dígitos \(X = abcdef\) satisfaz a propriedade de que \(abc-def\) é divisível por \(7\text{.}\) Prove que \(X\) também é divisível por \(7\text{.}\)

Solução
\begin{align*} X =\amp~ 10^3\cdot abc+def\\ =\amp~ (1001-1)\cdot abc+def\\ =\amp~ (1001)\cdot abc -abc+def\\ =\amp~ (1001)\cdot abc -(abc-def). \end{align*}

Como \(7|1001\) e \(7|abc-def\text{,}\) \(7|X\text{.}\)

6.

Encontre todos os inteiros positivos \(n\) tais que \(n+2009\) divide \(n^2+2009\) e \(n+2010\) divide \(n^2+2010\text{.}\)

Solução

Note que \(n=0\) e \(n=1\) são soluções, vamos mostrar que não existem outras soluções.

Note que

\begin{align*} n+2009|\amp~(n^2+2009)-(n+2009), \text{e}\\ n+2010|\amp~(n^2+2010)-(n+2010) \end{align*}

portanto

\begin{equation*} n+2009|n^2-n \quad \text{e} \quad n+2010|n^2-n\text{,} \end{equation*}

ou seja,

\begin{align*} n^2-n =\amp~ (n+2009)\cdot q\\ n^2-n =\amp~ (n+2010)\cdot \tilde{q}=(n+2009)\cdot\tilde{q}+\tilde{q}. \end{align*}

Portanto,

\begin{equation*} (n+2009)q=(n+2009)\tilde{q}+\tilde{q} \end{equation*}

e consequentemente,

\begin{align*} \tilde{q} =\amp~ (n+2009)q-(n+2009)\tilde{q}\\ =\amp~ (n+2009)\underbrace{(q-\tilde{q})}_{A}. \end{align*}

Então,

\begin{align*} n^2-n =\amp~ (n+2010)(n+2009)A\\ =\amp~ n^2A+n\cdot 2009\cdot A+n\cdot 2010\cdot A+2010\cdot 2009\cdot A \end{align*}

não possui solução, pois \(A=1\) e \(2010\cdot 2009\neq 0\text{.}\)

7.

Sejam \(n>1\) e \(k\) um inteiro positivo qualquer. Prove que \((n-1)^2|(n^k-1)\) se, e somente se, \((n-1)|k\text{.}\)

Solução
\begin{align*} \frac{n^k-1}{(n-1)^2}=\amp~\frac{(n-1)(n^{k-1}+n^{k-2}+\cdots+n+1)}{(n-1)^2}\\ =\amp~\underbrace{\frac{n^{k-1}}{n-1}+\frac{n^{k-2}}{n-1}+\cdots+\frac{n}{n-1}}_{k-1\text{ termos}}+\frac{1}{n-1}.\\ \end{align*}

Somando \(\frac{-1}{n-1}\) em cada termo exceto o último e subtraindo \(\frac{-1}{n-1}\cdot(k-1)\) no último termo:

\begin{equation*} \frac{n^k-1}{(n-1)^2}=\frac{n^{k-1}-1}{n-1}+\frac{n^{k-2}-1}{n-1}+\cdots+\frac{n-1}{n-1}+\frac{k}{n-1}. \end{equation*}

Como \(n-1\) divide \(n^{\alpha}-1\text{,}\) se \(\alpha\geq 1\text{,}\) \((n-1)^2|(n^k-1)\) se, e somente se, \((n-1)|k\text{.}\)

8. (Bielorússia 1996).

Inteiros \(m\) e \(n\text{,}\) satisfazem a igualdade

\begin{equation*} (m-n)^2 = \frac{4mn}{m+n-1}. \end{equation*}
  1. Prove que \(m+n\) é um quadrado perfeito.
  2. Encontre todos os pares \((m,n)\) satisfazendo a equação acima.
Solução

item a.

\begin{align*} (m-n)^2 =\amp~ \frac{4mn}{m+n-1}\\ (m-n)^2 +4mn=\amp~ \frac{4mn}{m+n-1}+4mn\\ m^2-2mn+n^2 +4mn=\amp~ \frac{4mn+4mn(m+n-1)}{m+n-1}\\ m^2+2mn+n^2 =\amp~ \frac{4mn(m+n)}{m+n-1}\\ (m+n)^2 =\amp~ \frac{4mn(m+n)}{m+n-1}\\ (m+n) =\amp~ \frac{4mn}{m+n-1}\\ (m+n)(m+n-1) =\amp~ 4mn\\ m^2+2mn-m+n^2-n =\amp~ 4mn\\ -(m+n) =\amp~ 4mn -m^2-2mn-n^2 \\ -(m+n) =\amp~ -m^2+2mn-n^2 \\ -(m+n) =\amp~ -(m-n)^2 \\ (m+n) =\amp~ (m-n)^2 \end{align*}

Assim, \((m+n)\) é o quadrado de um número.

item b. Se \(m-n=t\text{,}\) então \(m+n=t^2\text{.}\) Os pares de soluções são:

\begin{equation*} (m,n)=\left( \frac{t^2+t}{2}, \frac{t^2-t}{2} \right), ~~ t\in \mathbb{Z}. \end{equation*}