FANDOM


Sejam $ a $ e $ b $ inteiros. Dizemos que $ a $ é divisor de $ b $ (ou que $ a $ divide $ b $) quando existe um inteiro $ c $ tal que $ ac=b $. Neste caso, escreveremos $ a|b $. Caso contrário, escrevemos $ a \nmid b $.

Na definição acima, podemos dizer que $ a $ é um fator de $ b $.

Quando quisermos dizer que $ x|a_1 $, $ x|a_2 $,..., $ x|a_n $, podemos simplesmente escrever $ x|a_1,a_2,\dots,a_n $.

Algoritmo da Divisão Euclidiana Editar

Sejam $ a $ e $ b $ inteiros, com $ b $ diferente de $ 0 $. Então existem $ q $ e $ r $ inteiros tais que $ a=bq+r $ e $ 0 \leq r <|b| $.

Observação Editar

Os possíveis restos na divisão por $ n $ são $ 0,1,2,\dots,n-1 $.

ExemploEditar

Se $ n $ for um quadrado perfeito, prove que $ \sqrt{n}|n $.

Solução: Basta encontrarmos um $ c $ inteiro tal que $ \sqrt{n}.c=n $. Neste caso, $ c=\sqrt{n} $.

Exemplo Editar

Sejam $ a $ e $ b $ inteiros. Mostre que se $ a^2|b^2 $, então $ a|b $.

Solução: Se $ a=0 $, o problema é trivial. Já se $ a $ é diferente de $ 0 $, como $ a^2|b^2 $, por definição, existe $ c $ inteiro tal que

$ a^2c=b^2 \Leftrightarrow \sqrt{c}=\frac{b}{a}. (*) $.

Se $ \sqrt{c} $ não fosse inteiro, então seria irracional. Mas $ (*) $ nos diz que ele é racional. Logo, $ \sqrt{c} $ é inteiro. Com isso, $ c $ é quadrado perfeito, isto é, existe $ d $ inteiro tal que $ c=d^2 $.

Desta forma,

$ a^2d^2=b^2 \Leftrightarrow a(\pm d)=b \Leftrightarrow a|b. $

PropriedadesEditar

(i) (Propriedade Reflexiva) $ a|a $

(ii) (Propriedade Transitiva) Se $ a|b $ e $ b|c $, então $ a|c $

(iii) $ 0|a \Leftrightarrow a=0 $.

(iv) Para todo $ a $ inteiro, vale que $ a|0 $.

(v) Para todo $ a $ inteiro, vale que $ 1|a $.

(vi) Se $ a|b $ e $ a|c $, então $ a|(b+c) $.

(vii) Se $ a|b $ e $ a|c $, então $ a|(b-c) $.

(viii) Se $ a|b $, então $ a|bc $, para todo $ c $ inteiro.

(viii) Se $ a|b $ e $ c|d $, então $ ac|bd $.

(ix) Sejam $ a $ e $ b $ inteiros, com $ a $ não nulo. Então $ a|b $ se, e somente se, $ \frac{b}{a}|a $.

(x) Se $ a|b $, então $ ac|bc $.

(xi) Se $ c $ é diferente de zero e $ ac|bc $, então $ a|b $.

(xii) Sejam $ a $, $ b $ e $ d $ inteiros, com $ d $ diferente de zero. Se $ d|b $, então $ b|a $ se, e somente se, $ \frac{b}{d}|\frac{a}{d} $.

(xiii) (Lema de Euclides) Se $ \operatorname {mdc}(a,b)=1 $ e $ a|bc $, então $ a|c $.

(xiv) Se $ \operatorname{mdc}(a,b)=1 $, $ a|c $ e $ b|c $, então $ ab|c $.

(xv) (Limitação) Sejam $ a $ e $ b $ inteiros, com $ b $ diferente de zero. Se $ a|b $, então $ |a| \leq |b| $.

(xvi) Se $ a|b $ e $ b|a $, então $ |a|=|b| $.

Ideias Importantes Editar

  • Faça uma combinação linear e faça algo "complicado" sumir da sua conta.
  • Quando a divisibilidade parecer não dar em nada, diminua a quantidade de possibilidades, usando a propriedade da limitação. Ela te dará uma quantidade não tão grande de casos para testar. Em alguns casos, basta testarmos caso por caso para terminarmos um problema.

Exemplo (OBM 2013 - 3ª Fase - Nível 2) Editar

Dado um número de dois dígitos chamamos de seu quadroido o número formado juntando os quadrados de seus dígitos na mesma ordem do número. Por exemplo, os quadroidos de $ 19,72,65 $ e $ 23 $ são $ 181,494,3625 $ e $ 49 $, respectivamente. Ache todos os números de dois dígitos que dividem seu quadroido.

Solução: Devemos encontrar, então, todos os números $ \overline{xy} $, onde $ x $ e $ y $ são algarismos e $ x $ é diferente de zero. O que acontece se elevarmos esses algarismos ao quadrado? Depende.

Se elevarmos ao quadrado um algarismo menor que $ 4 $, então o resultado terá apenas um algarismo. Caso contrário, o resultado terá dois algarismos. Por isso devemos analisar cada caso separadamente.

1º Caso: $ 1 \leq x \leq 3 $ e $ 0 \leq y \leq 3 $

Neste caso, o quadroido de $ \overline{xy} $ é igual a $ 10x^2+y^2 $. Então dizer que $ \overline{xy} $ divide o seu quadrodio equivale a

$ 10x+y|10x^2+y^2. (*) $

Façamos uma combinação linear, para simplificar nossas contas. Para fazermos aparecer $ 10x^2 $ novamente, observe que

$ 10x+y|x(10x+y)=10x^2+xy. $

Com isso,

$ 10x+y|10x^2+y^2-(10x^2+xy)=y(y-x). $

Agora que a divisibilidade não nos parece dar muito, vamos usar a propriedade da limitação. Por ela, $ y(y-x)=0 $ ou $ |10x+y| \leq |y(y-x)| $. Analisemos cada possibilidade.

$ y(y-x)=0 \Leftrightarrow y=0 \textrm{ ou } y=x. $

Todas estas condições satisfazem $ (*) $. Logo, as soluções que conseguimos aqui são $ (x,y)=(1,0),(2,0),(3,0),(1,1),(2,2),(3,3) $, ou seja, os números são $ 10,20,30,11,22 $ e $ 33 $.

E quanto ao caso em que $ |10x+y| \leq |y(y-x)| $? Observe que

$ |10x+y|=10x+y \geq 10 $

e

$ |y(y-x)|=|y||y-x| \leq 3.3 = 9. $

Logo, não podemos ter $ |10x+y| \leq |y(y-x)| $.

2º Caso: $ 4 \leq x \leq 9 $ e $ 0 \leq y \leq 3 $

O quadroido de $ \overline{xy} $ continua sendo $ 10x^2+y^2 $. Pelo mesmo raciocínio do caso anterior,

$ 10x+y|y(y-x). $

Pela propriedade da limitação, continuamos tendo $ y(y-x)=0 $ ou $ |10x+y| \leq |y(y-x)| $. Neste caso, $ y(y-x)=0 $ nos dá os números $ 40,50,60,70,80 $ e $ 90 $.

E a informação $ |10x+y| \leq |y(y-x)| $ pode nos dar algo? Como $ y<x $, de onde segue que $ y-x<0 $, segue que $ |y-x|=-(y-x)=x-y $ podemos escrever a desigualdade como:

$ 10x+y \leq y(x-y) $.

Mas $ 10x+y \geq 40 $ e $ y(x-y) \leq 3.(9-0)=27 $. Logo, esta informação não nos dá nenhuma solução.

3º Caso: $ 4 \leq y \leq 9 $

Neste caso, $ y^2 $ possui dois algarismos e assim o quadroido de $ \overline{xy} $ é $ 100x^2+y^2 $. Assim,

$ 10x+y|100x^2+y^2. $

Seria legal se fizéssemos sumir a letra $ x $ do "lado direito da divisibilidade". Observe que

$ 10x+y|(10x+y)^2=100x^2+20xy+y^2. $

Com isso,

$ 10x+y|100x^2+20xy+y^2-(100x^2+y^2)=20xy. $

Além disso,

$ 10x+y|2y(10x+y)=20xy+2y^2. $

Com isso,

$ 10x+y|2y^2+20xy-20xy=2y^2. $

Analisemos cada uma das possibilidades para $ y $.

(i) $ y=4 $

A divisibilidade se torna

$ 10x+4|32 $.

Pela limitação,

$ 10x+4 \leq 32 \Leftrightarrow 10x \leq 28 $.

Como $ x $ é natural, segue que $ x=1 $ ou $ x=2 $ que não nos dá solução.

Podemos encontrar as soluções dos próximos casos usando o mesmo raciocínio.

(ii) $ y=5 $

Apenas $ x=2 $ é solução, o que nos dá o número $ 25 $.

(iii) $ y=6 $

Apenas $ x=3 $ é solução, o que nos dá o número $ 36 $.

(iv) $ y=7 $

Não existe solução neste caso.

(v) $ y=8 $

Não existe solução neste caso.

(vi) $ y=9 $

Não existe solução neste caso.

Portanto, todas as soluções são $ 10,20,30,11,22,33,40,50,60,70,80,90,25 $ e $ 36 $.

ProposiçãoEditar

Se $ a $ e $ b $ são inteiros e $ p $ um número primo, então

$ p|ab \Rightarrow p|a \text{ ou } p|b $.

CorolárioEditar

Se $ x $ é inteiro, $ n $ inteiro positivo e $ p $ é um número primo, então

$ p|x^n \Rightarrow p|x. $

Páginas RelacionadasEditar

Teorema Fundamental da Aritmética

Aritmética Modular

BibliografiaEditar

  • E. Lozansky, C. Rousseau : Winning Solutions, Springer-Verlag, New York, 1996.
  • T. Andreescu, D. Andrica, Z. Feng : 104 Number Theory Problems, Birkhauser, Boston 2006