Praticando a Aritmética   Lacerda [www.souexatas.blogspot.com.br] [materialcursoseconcursos.blogspot.com.br]
649 pág.

Praticando a Aritmética Lacerda [www.souexatas.blogspot.com.br] [materialcursoseconcursos.blogspot.com.br]


DisciplinaEstatística I20.477 materiais107.053 seguidores
Pré-visualização50 páginas
1.963
\u201cMain\u201d
2006/12/15
page 184
184 [CAP. 4: TEORIA DOS NU´MEROS PRIMOS EM N
\u201cMain\u201d
2006/12/15
page 185
Cap´\u131tulo 5
Divisibilidade
5.1 Introduc¸a\u2dco
Sejam A e B dois nu´meros naturais. Diz-se que A divide B, se existir um
nu´mero natural K tal que B = A× K.
Exs.: 4 divide 20 pois, 20 = 4× 5
7 divide 35 pois, 35 = 7× 5
5.1.1 Terminologias
A divide B, A e´ divisor de B, B e´ divis´\u131vel por A, B e´ mu´ltiplo de A.
5.1.2 Teorema
Se um nu´mero B dividir outro A, enta\u2dco dividira´ todos os mu´ltiplos de A.
Hip:
A
B
(A\u2d9 = A1, A2, A3, . . . )
Tese:
A1
B
,
A2
B
,
A3
B
, . . .
Demonstrac¸a\u2dco:
1o ) Se B divide A, enta\u2dco, A = B\u2d9
2o ) Seja K×A um mu´ltiplo de A, logo, K×A = K× (B\u2d9), enta\u2dco, K×A = B\u2d9 . . .
c.q.d
185
\u201cMain\u201d
2006/12/15
page 186
186 [CAP. 5: DIVISIBILIDADE
5.1.3 Corola´rio
A soma ou diferenc¸a dos mu´ltiplos de um nu´mero sa\u2dco mu´ltiplos desse nu´mero.
De acordo com esse corola´rio, podemos escrever que:
mult.A+mult.B+mult.C+ · · · = mult.(A+ B+ C+ . . . ) e,
mult.A\u2212mult.B\u2212mult.C\u2212 · · · = mult.(A\u2212 B\u2212 C\u2212 . . . )
5.2 Congue\u2c6ncia
5.2.1 Nu´meros Congruentes
Dois nu´meros se dizem congruentes ou co\u2c6ngruos quando, ao serem divididos
pelo mesmo divisor d (tambe´m chamado de mo´dulo), gerarem o mesmo resto.
Supondo A e B nu´meros dados . . .
A
\u2223\u2223d B \u2223\u2223d
r q1 r q2
Para indicar a congrue\u2c6ncia1 dos nu´meros A e B, usa-se a seguinte notac¸a\u2dco:
A \u2261 B (mod. d) ou A \u2261 B(d)
Leia-se: A congruente com B, mo´dulo d.
Obs.: A notac¸a\u2dco A \u2261 B (mod. d) e´ devida a Leibiniz.
Ex.: 14 \u2261 23(mod. 3)
Observe que 14÷ 3\u21d2 resto 2 e 23÷ 3\u21d2 resto 2.
5.2.2 Princ´\u131pios
1o ) Todo nu´mero e´ congruente consigo mesmo em relac¸a\u2dco a qualquer mo´dulo.
2o ) Todo mu´ltiplo de um nu´mero A e´ congruente com zero, mo´dulo d.
A\u2d9 \u2261 0(mod. d)
3o ) Todo nu´mero A e´ congruente com o resto da divisa\u2dco de mo´dulo d.
A \u2261 r(mod. d)
1As congrue\u2c6ncias foram introduzidas formalmente por K. F. Gauss (1.777\u22121.855) em sua
obra Disquisitiones Arithmeticae - 1.801
\u201cMain\u201d
2006/12/15
page 187
[SEC. 5.2: CONGUE\u2c6NCIA 187
5.2.3 Propriedades
1a ) A condic¸a\u2dco necessa´ria e suficiente para que dois nu´meros A e B sejam con-
gruentes em relac¸a\u2dco a um mesmo mo´dulo (d) e´ que sua diferenc¸a seja mu´ltipla
do mo´dulo.
A = d× q+ r \u2234 A = d\u2d9+ r . . . (I)
B = d × q \u2032 + r \u2234 B = d\u2d9+ r . . . (II)
A\u2212 B = d× (q\u2212 q \u2032) + r\u2212 r\u21d2 A\u2212 B = d\u2d9 . . . (III)
Substituindo (II) em (III), teremos: A = d\u2d9 + r+ d\u2d9 \u2234 A = d\u2d9+ r
Portanto . . .A \u2261 B(mod. d) . . . c.q.d.
2a ) Podemos somar (ou subtrair), membro a membro, duas congrue\u2c6ncias de
mesmo mo´dulo.
Se A \u2261 a(mod. d)\u21d2 A = d\u2d9+ a . . . (I)
Se B \u2261 b(mod. d)\u21d2 B = d\u2d9 + b . . . (II)
(I) + (II)
A+ B = d\u2d9+ a + d\u2d9+ b
A+ B = d\u2d9+ a + b
A+ B \u2261 (a + b)(mod. d)
O mesmo racioc´\u131nio se aplica a` subtrac¸a\u2dco.
3a ) Dois nu´meros co\u2c6ngruos com um terceiro de mesmo mo´dulo sa\u2dco co\u2c6ngruos
entre si .
Se A \u2261 B(mod. d) e se B \u2261 C(mod. d), enta\u2dco A \u2261 C(mod. d)
A\u2212 B = d\u2d9 e B \u2212C = d\u2d9
Somando-se membro a membro, teremos:
(A\u2212 B) + (B\u2212 C) = d\u2d9 + d\u2d9 ou A\u2212 C = d\u2d9\u21d2 A \u2261 C(mod. d) . . . c.q.d.
4a ) Podemos somar ou subtrair o mesmo nu´mero k aos dois membros de uma
congrue\u2c6ncia.
Hip: A \u2261 B(mod. d) . . . (I)
Tese: A + k \u2261 [B+ k](mod. d)
De (I) podemos afirmar que A\u2212 B = d\u2d9
\u201cMain\u201d
2006/12/15
page 188
188 [CAP. 5: DIVISIBILIDADE
A+ k \u2212 (B + k) = A\u2212 B = d\u2d9 ou
A+ k = B+ k+ d\u2d9 \u2234 A+ k \u2261 [B+ k](mod. k) . . . c.q.d.
Aplicar o mesmo racioc´\u131nio para a subtrac¸a\u2dco.
5.2.4 Corola´rio
Podemos transpor os termos de uma congrue\u2c6ncia de um membro a outro
desde que troquemos os seus sinais.
5a ) Podemos multiplicar os dois membros de uma congrue\u2c6ncia por um mesmo
nu´mero.
Se A \u2261 B(mod. d) enta\u2dco A × k = B× k (mod. d)
Com efeito, se A\u2212 B = d\u2d9, deduz-se que (A\u2212 B) × k = d\u2d9
A× k \u2212 B × k = d\u2d9 ou A× k = B × k + d\u2d9 \u2234 A× k = B × k (mod. d)
6a ) Podemos multiplicar, membro a membro, duas congrue\u2c6ncias de mesmo
mo´dulo.
Se A \u2261 a(mod. d) e B \u2261 b(mod. d), enta\u2dco A× B \u2261 a × b(mod. d)
Com efeito, ja´ que A = d\u2d9+ a e B = d\u2d9+ b, enta\u2dco
A× B = d\u2d9+ a× b \u2234 A× B = a × b (mod. d) . . . c.q.d.
5.2.5 Corola´rio
Podemos elevar os dois membros de uma congrue\u2c6ncia ao mesmo expoente.
Se A \u2261 B (mod. d), A \u2261 B (mod. d), . . .A \u2261 B (mod. d), enta\u2dco . . .
A×A× · · · ×A\ufe38 \ufe37\ufe37 \ufe38
m fatores
\u2261 [B× B × · · · × B\ufe38 \ufe37\ufe37 \ufe38
m fatores
](mod. d) \u2234 Am \u2261 Bm(mod. d) . . .
c.q.d.
deduz-se que Am \u2261 Bm(mod. d)
7a ) Podemos suprimir um fator comum aos dois membros e ao mo´dulo da
congrue\u2c6ncia.
Se k× A = k× B (mod. k× d), enta\u2dco A \u2261 B (mod. d)
Com efeito, k× A\u2212 k× B \u2261 d\u2d9
\u201cMain\u201d
2006/12/15
page 189
[SEC. 5.3: TEOREMA FUNDAMENTAL DA DIVISIBILIDADE 189
k×A \u2212 k × B \u2261 k× d × q
Sendo q um nu´mero natural, enta\u2dco, A \u2212 B = d × q \u21d2 A = B + d\u2d9 \u2234
A \u2261 B (mod. d) . . . c.q.d
8a ) Se P(x) e´ um polino\u2c6mio alge´brico e se a \u2261 b(mod. d), enta\u2dco P(a) \u2261
P(b)(mod. d)
Seja P(x) = Axn + Bxn\u22121 + · · ·+ Kx+ L
Se a \u2261 b(mod. d), deduz-se que:
A× an \u2261 A× bn(mod. d)
B× an\u22121 \u2261 B× bn\u22121(mod. d)
...
k× a \u2261 k× b(mod. d)
L \u2261 L(mod. d)
Somando membro a membro, teremos:
P(a) \u2261 P(b)(mod. d) . . . c.q.d.
9a ) Se dois nu´meros A e B forem congruentes em relac¸a\u2dco a va´rios mo´dulos,
enta\u2dco sera\u2dco congruentes ao m.m.c deles.
10a ) Em toda congrue\u2c6ncia, o m.d.c de um membro e o mo´dulo e´ igual ao do
outro membro e o mo´dulo.
5.3 Teorema Fundamental da Divisibilidade
Se um nu´mero d divide uma de duas parcelas A e B de uma adic¸a\u2dco, a soma
S e a outra parcela sera\u2dco congruentes em relac¸a\u2dco a esse divisor .
Hip. A + B = S e d|A
Tese: S \u2261 B (mod. d)
Demonstrac¸a\u2dco:
1o ) Se d e´ divisor de A, enta\u2dco, A = d\u2d9;
2o )
B
d
= q1 + r\u2192 B = d× q1 + r \u2234 B = d\u2d9+ r . . . (I)
3o ) Se A+ B = S\u2192 d\u2d9+ d\u2d9+ r = S\u2192 S = d\u2d9+ r . . . (II)
De (I) e (II), podemos escrever que:
S \u2261 B (mod. d) . . . c.q.d.
\u201cMain\u201d
2006/12/15
page 190
190 [CAP. 5: DIVISIBILIDADE
5.3.1 Teorema
Se va´rios nu´meros A,B,C, . . . forem divididos por um mesmo divisor d,
a soma S desses nu´meros e a soma dos restos r1 + r2 + r3 + . . . , ou seja,
Sr, obtidos dessas diviso\u2dces por esse divisor, sera\u2dco congruentes em relac¸a\u2dco ao
mesmo divisor .
Hip.:
A
d
,
B
d
,
C
d
. . .
Tese: S \u2261 Sr (mod. d)
Demonstrac¸a\u2dco:
A
d
= q1 + r1 \u2192 A = d × q1 + r1 \u2234 A = d\u2d9+ r1;
B
d
= q2 + r2 \u2192 B = d× q2 + r2 \u2234 B = d\u2d9 + r2;
C
d
= q3 + r3 \u2192 C = d× q3 + r3 \u2234 C = d\u2d9+ r3
...
Somando-se as igualdades anteriores, membro a membro, teremos:
A+ B +C+ · · · = (d\u2d9+ r1) + (d\u2d9+ r2) + (d\u2d9 + r3) + . . . ou
A+ B +C+ · · · = d\u2d9+ d\u2d9+ d\u2d9+ . . .\ufe38 \ufe37\ufe37 \ufe38
d\u2d9
+ r1 + r2 + r3 + . . .\ufe38 \ufe37\ufe37 \ufe38
Sr
ou ainda,
S = d\u2d9+ Sr
Dividindo-se os dois membros por d e aplicando o Teorema Fundamental
da Divisibilidade (T.F.D), podemos escrever que:
S \u2261 Sr (mod. d) . . . c. q. d.
5.3.2 Teorema
Dividindo-se va´rios nu´meros A,B,C, . . . pelo mesmo divisor d, o produto
P desses nu´meros e o produto dos restos Pr dessas diviso\u2dces por esse divisor,
sera\u2dco congruentes em relac¸a\u2dco ao mesmo divisor .
Hip.:
A
d
,
B
d
,
C
d
. . .
Tese: P \u2261 Pr (mod. d)
\u201cMain\u201d
2006/12/15
page 191
[SEC. 5.3: TEOREMA FUNDAMENTAL DA DIVISIBILIDADE 191
Demonstrac¸a\u2dco:
Tomemos, inicialmente, os nu´meros A e B, e para divisor o nu´mero d.
A
\u2223\u2223d . . . (I) B \u2223\u2223d . . . (II)
r1 q1 r2 q2
De (I) e (II), podemos escrever que:
1o ) A = d× q1 + r1 ou A = d\u2d9+ r1 . . . (III)
2o ) B = d × q2 + r2 ou B = d\u2d9+ r2 . . . (IV)
Multiplicando-se (III) por (IV), membro a membro, teremos:
A× B = (d\u2d9+ r1) × (d\u2d9 + r2) ou
A× B = d\u2d9× d\u2d9+ r1 × d\u2d9+ r2 × d\u2d9+ r1 × r2
A× B = d\u2d9+ r1 × r2
Se tomarmos tre\u2c6s fatores e fizermos um desenvolvimento ana´logo ao ante-
rior, concluiremos que:
A× B ×C = d\u2d9 + r1 × r2 × r3
Para n fatores, isto e´, A× B× C× . . . , teremos,
A× B ×C× . . .\ufe38 \ufe37\ufe37 \ufe38
P
= d\u2d9+ r1 × r2 × r3 × . . .\ufe38 \ufe37\ufe37 \ufe38