Matemática Discreta II - texto 7 - 1

SAVE OFFLINE

UEM-CCE-DMA – 6880 / 5173 – MATEMÁTICA DISCRETA II – 2/2015. CURSOS: Ciências da Computação / Informática Texto 7 9. Aritmética Modular: Congruência Módulo m / Inteiros módulo m. 9.1. Congruência Módulo m Euler já utilizava em algumas de suas demonstrações os “restos da divisão por p” que deram origem à Teoria das Congruências. Lagrange e Legendre também utilizaram esse método de trabalho, mas quem o formalizou foi Gauss, em 1801, no livro “ Disquisitiones Arithmeticae”, no qual aparecem a definição precisa e o simbolismo que se usa até hoje. Veremos nesse texto, através de exemplos, que congruências simplificam bastante o estudo de muitas questões de divisibilidade.

DEFINIÇÃO 9.1.1 Seja m um inteiro não nulo. Diz-se que dois inteiros a e b são congruentes módulo m se os restos de suas divisões por m são iguais. Notação: No lugar de “a é congruente a b módulo m”, escreve-se “ a ≡ b (mod m)”. Quando os restos das divisões de a e b por m não forem iguais, diremos que a não é congruente a b módulo m e escrevemos “ a ≡ b (mod m)”. Exemplos: 1) 56 ≡ 11 (mod 5), pois os restos da divisão de 56 e 11 por 5 são iguais a 1. 2) 79 ≡ 44 (mod 11), pois o resto da divisão de 79 por 11 é 2, enquanto o resto da divisão de 44 por 11 é 0.

PROPOSIÇÃO 9.1.1 Seja m um inteiro não nulo e sejam a e b inteiros. a ≡ b (mod m) se, e somente se, m \ (b – a). Demonstração: Considerando as divisões de a por m e de b por m, podemos escrever a = mq + r , com 0 ≤ r ≤ m e q algum inteiro e b = mq’ + r’, com 0 ≤ r’ ≤ m e q’ algum inteiro . Assim, b – a = m(q’ – q) + ( r’ – r).

(1)

Portanto, a ≡ b (mod m) se, e somente se, r’ = r, ou seja se, e somente se r’ – r = 0, que, por (1), é equivalente a dizermos que m divide b – a . ■

Exemplos: 3) 327 ≡ −13 (mod 17), pois 327 – (– 13) = 340 que é divisível por 17. 4) 1.578

≡ 176 (mod 3), pois 1.578 – 176 = 1.402 que não é divisível por 3.

OBSERVAÇÕES: 1. Como m \( b – a) a considerar o caso em que m > 0.

se, e somente se, |m| \ (b – a), limitar-nos-emos

2. Como o resto da divisão de um número inteiro qualquer por 1 é sempre nulo, é desinteressante considerarmos o caso m = 1, pois a ≡ b (mod 1) , quaisquer que sejam a e b inteiros. Com essas observações, passaremos a considerar apenas os casos em que m > 1.

Estabelecemos, no próximo resultado, que a congruência módulo m é uma relação de equivalência.

PROPOSIÇÃO 9.1.2 Seja m um inteiro fixo e m > 1. Quaisquer que sejam a, b e c inteiros, tem-se que: i) a ≡ a (mod m); ii) Se a ≡ b (mod m) , então b ≡ a (mod m); iii) Se a ≡ b (mod m) e b ≡ c (mod m), então a ≡ c (mod m).

Demonstração: i) e ii) decorrem de imediato da definição de congruência módulo m. iii) Se a ≡ b (mod m) e b ≡ c (mod m), então m \( b – a) e m \( c – b) . Assim, m \ [(c – b) + (b – a)] , ou seja m \( c – a), e portanto, a ≡ c (mod m) . ■ Os próximos resultados estabelecem a compatibilidade da relação de congruência módulo m com as operações de adição, subtração e multiplicação em Z. PROPOSIÇÃO 9.1.3 Seja m um inteiro fixo e m > 1. Quaisquer que sejam a, b e c inteiros, tem-se que: ii) Se a ≡ b (mod m), então a ± c ≡ b ± c (mod m). iii) Se a ≡ b (mod m), então a·c ≡ b·c (mod m). Demonstração: i) Se a ≡ b (mod m), então m \( b – a), mas b – a = (b ± c) – (a ± c); logo, pela Proposição 9.1.1, a ± c ≡ b ± c (mod m).

ii) Deixamos essa demonstração como exercício (Veja lista 13 de exercícios) ■ PROPOSIÇÃO 9.1.4 Seja m um inteiro fixo e m > 1. Quaisquer que sejam a, b, c e d inteiros, tem-se que: i) Se a ≡ b (mod m) e c ≡ d (mod m), então a ± c ≡ b ± d (mod m). ii) Se a ≡ b (mod m) e c ≡ d (mod m), então a·c ≡ b·d (mod m). Demonstração: i) Deixamos como exercício (veja lista 13 de exercícios). ii) Se a ≡ b (mod m) e c ≡ d (mod m), então existem q1 e q2 tais que b – a = q1·m e d – c = q2·m, ou seja b = a + q1·m e d = c + q2·m. Então, b·d = a·c +( aq2 + cq1 + q1q2m)·m, que equivale a b·d − a·c = ( aq2 + cq1 + q1q2m)·m. Portanto, a·c ≡ b·d (mod m). ■ COROLÁRIO. Seja m um inteiro fixo e m > 1. Quaisquer que sejam a e b inteiros, tem-se que: “ se a ≡ b (mod m) , então an ≡ bn (mod m), qualquer que seja n∈ ℤ*+ . Demonstração: A demonstração é feita por indução sobre n e não apresenta nenhuma dificuldade, portanto é omitida neste texto. ■ Exemplos: 5) Determine o resto da divisão de 740 por 50. Resolução: O algoritmo da divisão por 50 nos dá que 740 = 50 q + r, para certos valores de q, r ∈ Z, com 0 ≤ r < 50. Assim devemos determinar o inteiro r tal que 0 ≤ r < 50 e 740 − r = 50 q , isto é, r ≡ 740 (mod 50). Sabemos que 72 = 49, portanto −1 ≡ 72 (mod 50). Usando o Corolário, acima, vemos que (−1)2 ≡ (72)2 (mod 50) ; isto é, 1 ≡ 74 (mod 50). Usando esse Corolário novamente, 1 ≡ 740 (mod 50). Assim, r = 1.

temos que

110 ≡ (74)10 (mod 50), ou seja,

6) Determine o resto da divisão de a = 1 + 2 + 22 + 23 + 24 + ... + 2100 por 8. Resolução: a = 1 + 2 + 22 + 23 + 24 + ... + 2100 = 1 + 2 + 4 + 8 + 8·2 + ...+ 8. 297. Logo, a = 7 + 8 ( 1 + 2 + 22 + ... + 297) . Assim, a – 7 = 8 ( 1 + 2 + 22 + ... + 297) Ou seja, a ≡ 7 (mod 8). Assim, o resto da divisão de a por 8 é 7.

7) Determine o algarismo da unidade do número 3100 . Resolução: Devemos observar inicialmente que, quando representamos um número a na base 10, obtemos a = rn10n + rn−1 10n−1 + .. .+ r2102 + r110 + r0, em que r0 é o resto da divisão de a por 10. Ou seja, a ≡ r0 (mod 10). Assim, se determinarmos um número inteiro x, com 0 ≤ x < 10, tal que 3100 ≡ x (mod 10), estaremos determinando o algarismo da unidade em sua representação decimal. Observemos inicialmente que 32 ≡ −1 (mod 10). Assim, 34 ≡ 1 (mod 10). Portanto, 3100 = (34)25 ≡ 1 (mod 10). Determinamos, dessa forma, que 1 é o algarismo da unidade na representação decimal de 3100.

8) Vamos obter o critério de divisibilidade por 11, usando congruências. Consideremos a representação decimal do número a : a = rn10n + rn−1 10n−1 + ... + r2102 + r110 + r0, em que 0 ≤ ri ≤ 9 , i = 0, 1, 2, .., n . e rn ≠ 0. Como 10 ≡ −1 (mod 11), então temos que i

10 ≡ −1 (mod 11), se i é ímpar e

i

10 ≡ 1 (mod 11), se i é par.

Assim, rn10n ≡ (−1)n rn (mod 11),

rn−1 10n−1 ≡ (−1)n−1rn−1 (mod 11), ⁞ r2102 ≡ r2 (mod 11) , r110 ≡ − r1 (mod 11) e r0 ≡ r0 (mod 11). Assim, sendo a = rn10n + rn−1 10n−1 + ... + r2102 + r110 + r0, então a ≡ (−1)n rn + (−1)n−1 rn−1+ ... + (−1) r1 + r0 ( mod 11) Logo, a ≡ [(r0 + r2 + ....) − (r1 + r3 + ....)] (mod 11) Consequentemente, a é divisível por 11 se, e somente se, 11 \ [(r0 + r2 + ....) − (r1 + r3 + ....)]. Por exemplo, • • •

935 é divisível por 11, pois ( 5 + 9) – 3 = 11. 2.849.506 é divisível por 11, pois (6 + 5 + 4 + 2 ) – (0 + 9 + 8 ) = 17 – 17 = 0. 132.567 não é divisível por 11, pois (7 + 5 + 3) – (6 + 2 + 1) = 15 – 9 = 6 que não é divisível por 11.

PROPOSIÇÃO 9.1.5 Seja m um inteiro fixo e m > 1. Quaisquer que sejam a, b e c inteiros, tem-se que: i) Se a ± c ≡ b ± c (mod m), então a ≡ b ( mod m). ii) Se a·c ≡ b·c (mod m) e mdc (c, m) = d, sendo d ≥ 1, então a ≡ b ( mod m/d ). iii) Se a·c ≡ b·c (mod m) e mdc (c, m) = 1, então a ≡ b ( mod m). Demonstração: i) Deixamos como exercício (veja lista 13 de exercícios). ii) Se a·c ≡ b·c (mod m), então (b – a)·c = b·c − a·c = k·m, para algum k∈Z. Portanto, (b – a)·c = k·m.

Sendo mdc (c, m) = d, podemos dividir ambos os membros da última

igualdade por d, obtendo (b – a)·(c/d ) = k·(m/d). Assim, temos que m/d divide (b – a)·(c/d ) . Mas mdc (c/d, m/d) = d/d = 1. Logo, m/d divide b – a, o que significa que a ≡ b ( mod m/d ). iii) Segue imediatamente do item anterior. ■

LISTA 13 DE EXERCÍCIOS

1. Demonstre a Proposição 9.1.3 ii). 2. Demonstre a Proposição 9.1.4 i). 3. Demonstre a Proposição 9.1.5 i). 4. Seja m um inteiro fixo e m > 1. Mostre que, para quaisquer inteiros a, b, c e d, tem-se que: a) Se a + b ≡ 0 (mod m) e c + d ≡ 0 (mod m) , então a·c ≡ b·d (mod m) b) Se a ≡ b ( mod m) e c + d ≡ 0 (mod m) , então a·c + b·d ≡ 0 (mod m). c) Se a ≡ b + c (mod m), então a − c ≡ b (mod m). d) ( a – m)2 ≡ a2 (mod m) e ( m – a)2 ≡ a2 (mod m).

5. Determine o número inteiro x, tal que 0 ≤ x < 11, de modo que x ≡ 23·38·2·13 (mod 11).

6. Determine o resto da divisão de a) 710 por 51 b) 2100 por 11 d ) 521 por 127

e) (116 + 1717)21 por 8

g) 1! + 2! +3! + ...+ (1010)! por 40

c) 4165 por 7 f) 1316 – 225·515 por 3 h) 15+25+35+ ... + 1005 por 4

7. Use congruências para verificar que a) 89 \ (244 – 1 ) b) 23 \ 211 – 1 ) ================================================================= 9.2 CONGRUÊNCIAS LINEARES 9.2.1 Conceituação. Uma congruência do tipo aX ≡ b (mod m), em que a, b são constantes inteiras, m é um inteiro fixo, m >1, e X é uma variável em Z, é o que entenderemos por “congruência linear”. 9.2.2 Soluções. Uma solução de uma congruência linear aX ≡ b (mod m), é um valor inteiro X = x0 que satisfaça a congruência.

Exemplos: 1) X = 2 é solução da congruência linear 2X ≡ 1 (mod 3), o que obviamente não ocorre com X = 3.

OBSERVAÇÃO: 1) Se x ∈Z é uma solução de aX ≡ b (mod m) , então m \ (b – ax), o que equivale a que exista y ∈Z,

tal que b – ax = my ou

ax + my = b. Logo, (x, y) é uma solução da

equação diofantina aX + mY = b. Reciprocamente, se (x, y) é uma solução da equação diofantina aX + mY = b, então temos que ax + my = b, ou que b – ax = my, de modo que m \ (b – ax), o que equivale a x ser solução da congruência linear aX ≡ b (mod m). Demonstramos, assim, a seguinte proposição.

PROPOSIÇÃO 9.2.1 Sejam a, b constantes inteiras e seja m um inteiro fixo, m >1. Seja d = mdc (a, m). A congruência linear

aX ≡ b (mod m), possui solução se, e somente

se, a equação diofantina aX + mY = b possui solução, ou seja, se, e somente se, d \ b. ■

OBSERVAÇÃO: 2) Vimos, no texto 6, que sendo d = mdc (a, m) e d =a x0 + my0 , para algum inteiro x0 e para algum inteiro y0 , então toda solução da equação diofantina aX + mY = b é da ( x0 ⋅ b + m t, y0 ⋅ b − a t ) com t ∈Z. forma d d d d Consequentemente, nas condições acima, todas as soluções da congruência linear aX ≡ b (mod m) são da forma

x0 ⋅ b + m t com t ∈Z. d d

Atribuindo os valores t = 0, 1, 2, ... , d – 1, em x0 ⋅ b + m t , obtemos o conjunto de d d b b m b 2m  soluções  x0 ⋅ , x0 ⋅ + , x0 ⋅ + , ... , x0 ⋅ b + (d – 1)m  . d d d d d d d   É possível demonstrarmos que as soluções do conjunto acima são duas a duas não congruentes módulo m. E mais, toda solução da congruência aX ≡ b (mod m) é congruente a uma, e somente uma, solução desse conjunto.

TEOREMA 9.2.1 Sejam a, b constantes em Z e seja m um inteiro fixo, m >1. Seja d = mdc (a, m). Se d =a x0 + my0 , para algum inteiro x0 e para algum inteiro y0 , então a congruência linear aX ≡ b (mod m) possui soluções no conjunto

b b m b 2m  ,  x0 ⋅ , x0 ⋅ + , x0 ⋅ + d d d d d 

... ,

b (d – 1)m  x0 ⋅ + , d d 

sendo essas, duas a duas, não congruentes módulo m. E mais, toda solução da congruência linear dada é congruente módulo m a uma dessas soluções. O conjunto, dado acima, é denominado um “sistema de soluções módulo m” da congruência linear dada. ( Não apresentaremos, nesse texto, uma demonstração do teorema acima). ■

COROLÁRIO. Nas condições do teorema acima, se d = mdc (a, m) = 1, então a congruência linear aX ≡ b (mod m) sempre possui solução e toda solução é congruente a x = x0 b.

Exemplo: 2) Resolva a congruência −3x ≡ 18 (mod15). Resolução:

mdc (−3, 15) = 3 e 3 = 4·(−3) + 1·15. Assim, x0 = 4 e b/d = 18 / 3 = 6.

Assim, toda solução é congruente módulo 15 a uma das seguintes soluções 15 2 ⋅ 15 , 4 ·6 + } = {24, 29, 34} . Dizemos que estas são todas as 3 3 soluções módulo 15 da congruência dada.

{ 4 ·6, 4 ·6 +

Em verdade o conjunto solução é o conjunto { 24+ 5t / t∈Z }, mas as três soluções obtidas acima representam todas as soluções, módulo 15. Por exemplo, −26 é solução da congruência pois, (−3)(−26) = 78 ≡ 18 (mod 15) e −26 ≡ 34 (mod 15); 39 é outra solução da congruência pois, (−3)(39) = −107 ≡ 18 (mod 15) e 39 ≡ 24 (mod 15); uma outra solução é −91, pois (−3)(−91) = 273 ≡ 18 (mod 15) e −91≡ 29 (mod 15).

LISTA 14 DE EXERCÍCIOS 1. Resolva, se possível, as seguintes congruências lineares: a) 3X ≡ 5 (mod 7) b) 25X ≡ 15 (mod 29) c) 6X ≡ 21 (mod 18) d) 5X ≡ 2 (mod 26) e) 12X ≡ 36 (mod 28) f) 140X ≡ 133 (mod 301)

2. Pode o dobro de um número inteiro deixar resto igual a 9 quando dividido por 26? Sim ou não com justificativa. E quando dividido por 25? 3.Determine todas as soluções da congruência linear em duas variáveis: 3X – 7Y≡ 11 (mod 13).

9.3 INTEIROS MÓDULO m ATENÇÃO: Em toda esta seção, m indicará um inteiro fixo maior do que 1.

DEFINIÇÃO 9.3.1 Seja a um inteiro. O conjunto de todos os inteiros congruentes a a módulo m, denotado por a , é denominado “classe de congruência de a módulo m”.

Assim,

a = { x ∈ ℤ / x ≡ a ( mod m ) } = { x ∈ ℤ / x − a = tm para algum t ∈ ℤ } e, portanto,

a = { x ∈ ℤ / x = a + tm para algum t ∈ ℤ } = {a + tm / t ∈ ℤ } .

PROPOSIÇÃO 9.3.1 Sejam a e b inteiros. Tem-se que, a ≡ b (mod m) se, e somente se, a = b . Demonstração: Suponhamos que a ≡ b (mod m). Queremos demonstrar que a = b .

Seja x ∈ a . Assim, x ≡ a (mod m). Como a ≡ b (mod m), por transitividade da relação ≡, temos que x ≡ b (mod m); logo, x ∈ b e temos demonstrado que a ⊂ b . A inclusão b ⊂ a é demonstrada de modo análogo. Assim, a = b .

Reciprocamente, se a = b , como a ∈ a , então temos também que a ∈ b . Logo, a ≡ b (mod m).

■ COROLÁRIO. Sejam a e b inteiros. Tem-se que, se a ≠ b , então a ∩ b = ∅. Demonstração: Vamos demonstrar a contrapositiva dessa afirmativa: “ Se a ∩ b ≠ ∅ ,

então a = b ”. Se a ∩ b ≠ ∅ , então existe c ∈Z, tal que c ∈ a e c ∈ b . Então e

c ≡ a (mod m)

c ≡ b (mod m). Segue-se que a ≡ b (mod m), e da proposição anterior, a = b .

■ OBSERVAÇÕES: 1) Qualquer que seja x∈ a , temos que x ≡ a (mod m), consequentemente, x = a.

e

Em vista disso, tanto a, quanto qualquer um de seus elementos, é um representante de sua classe de congruência módulo m. Exemplificamos esse fato considerando classes de congruência módulo 3.

2 = { 2 + 3t / t ∈ ℤ} = {... − 4, − 1, 2, 5, ...} é representado, por exemplo, por 2, por – 4 , por – 1, por 5, assim como, por qualquer número da forma 2 + 3t, t ∈Z. 2) Sabemos que todo número inteiro z é congruente ao seu resto pela divisão por m. Como os restos da divisão por m são iguais a 0, 1, 2, ..., m – 1, então z é congruente a um desses números. Além disso, quaisquer dois números distintos em {0, 1, 2, ... m – 1}, não são congruentes módulo m. Assim, para o inteiro m fixado, as classes de congruência módulo m estão todas no seguinte conjunto

{0, 1, 2, ... , m − 1}. À luz desta observação 2, introduzimos a definição a seguir.

DEFINIÇÃO 9.3.2 Dado um inteiro m (m > 1), o conjunto {0, 1, 2, ... , m − 1} é denominado o “conjunto dos inteiros módulo m” e é denotado por ℤ m .

EXEMPLO 1.

ℤ 5 = {0, 1, 2, 3, 4}. Está correto também escrevermos que

ℤ 5 = {10, −4, 32, 8, −16} , pois

10 = 0, −4 =1, 32 = 2, 8 = 3 e −16 = 4 . No entanto, fica mais claro se usarmos como representantes os restos 0, 1, 2, 3, e 4.

O conjunto ℤ m pode ser munido das operações de adição e de multiplicação. É o que veremos a seguir. Antes, porém, necessitamos do seguinte resultado.

PROPOSIÇÃO 9.3.2 Sejam a, a’, b e b’ inteiros. Em ℤ m , se a = a' e b = b' , então a + b = a' + b' e a ⋅ b = a' ⋅ b' .

Demonstração: Da Proposição 9.3.1 temos que a = a' e b = b' , se, e somente se, a ≡ a’ (mod m), e b ≡ b’ (mod m) e da Proposição 9.1.4 temos que a + a’≡ b + b’(mod m) e a · a’≡ b · b’(mod m). Novamente, pela Proposição 9.3.1, temos que a + b = a' + b'

e

a ⋅ b = a' ⋅ b' .

■ DEFINIÇÃO 9.3.3 Definimos a adição + : ℤm × ℤ m → ℤ m , por a + b = a + b . Definimos a multiplicação ⋅ : ℤm × ℤm → ℤ m , por a ⋅ b = a ⋅ b .

OBSERVAÇÃO 4) A proposição 9.3.2 nos garante que a definição acima independe dos representantes que escolhemos para definir a adição ou a multiplicação. Ou seja, a definição acima faz sentido.

EXEMPLO 2.

Em

ℤ 5 = {0, 1, 2, 3, 4}

temos que 0 + 0 = 0 + 0 = 0 ,

2 + 3 = 5 = 0,

4 + 3 = 7 = 2 , 0 ⋅ 4 = 0 , 1 ⋅ 3 = 3, 2 ⋅ 4 = 8 = 3 . Assim, temos as seguintes tábuas operatórias para ℤ 5 = {0, 1, 2, 3, 4} .

1 + 2 =1+ 2 = 3,

+ 0 1 2 3 4

0 0 1 2 3 4

1 1 2 3 4 0

2 2 3 4 0 1

3 3 4 0 1 2

· 0 1 2 3 4

4 4 0 1 2 3

0 0 0 0 0 0

1 0 1 2 3 4

2 0 2 4 1 3

3 0 3 1 4 2

4 0 4 3 2 1

Sempre que definimos operações em um conjunto nos perguntamos a respeito de suas propriedades.

PROPOSIÇÃO 9.3.3 As seguintes afirmativas são verdadeiras para a adição em ℤ m : i) (Associatividade) (∀ a, b, c ∈ ℤm )

(a + b ) + c = a + ( b + c ) .

ii) (Comutatividade) (∀ a, b ∈ ℤm ) a + b = b + a . iii) (Existência

do

neutro)

0 ∈ ℤm

é

o

único

elemento

que

satisfaz

a + 0 = 0 + a = a , ∀a ∈ℤm . iv) (Existência do oposto) Para cada a ∈ℤm , existe, em ℤm , o oposto a a , denotado por −a , no sentido de que a + (− a ) = 0 = (− a ) + a . E mais, − a = −a é o único em

ℤm que satisfaz essa propriedade. Demonstração: i) (∀ a, b, c ∈ ℤm )

( a + b ) + c = a + b + c = (a + b) + c = a + (b + c ) = a + b+ c = a + ( b + c ).

ii) (∀ a, b ∈ ℤm ) a + b = a + b = b + a = b + a .

iii) 0 ∈ ℤ m satisfaz a + 0 = a+ 0 = a e 0 + a = 0 + a = a , ∀a ∈ℤ m . Devemos mostrar que 0 é o único em ℤm que satisfaz essa propriedade. Seja b ∈ ℤm tal que a + b = a . Então, a + b = a + 0 , de onde temos que a + b = a + 0 que é equivalente a a + b ≡ a + 0 mod(m), que, por sua vez, implica

em que b ≡ 0 mod(m), ou seja b = 0 . iv) Para

cada

a ∈ℤm ,

existe

−a

em

ℤm ,

tal

que

a + (− a) = a + ( −a) = 0 = ( −a) + a = (− a ) + a . Assim, −a = −a . Vejamos que vale a unicidade. Seja b ∈ ℤm tal que a + b = 0 . Então

b = b + 0 = b + (a + (− a )) = (b + a ) + (− a ) = 0 + (− a) = (− a). ■

PROPOSIÇÃO 9.3.4 As seguintes afirmativas são verdadeiras para a multiplicação em ℤm :

(a ⋅ b ) ⋅ c = a ⋅ ( b ⋅ c ) .

i) (Associatividade) (∀ a, b, c ∈ ℤm )

ii) (Comutatividade) (∀ a, b ∈ ℤm ) a ⋅ b = b ⋅ a . iii) (Existência

do

neutro)

1 ∈ ℤm

a ⋅ 1 = 1 ⋅ a = a , ∀a ∈ℤ m .

é

(

o

único

elemento

que

satisfaz

)

iv) (Distributividade) (∀ a, b, c ∈ ℤm ) a ⋅ b + c = a ⋅ b + a ⋅ c , bem como,

(b + c ) ⋅a =

b ⋅a + c ⋅a .

Demonstração: i) (∀ a, b, c ∈ ℤm )

( a ⋅ b ) ⋅ c = a ⋅ b ⋅ c = (a ⋅ b ) ⋅ c = a ⋅ ( b ⋅ c ) = a ⋅ b ⋅ c = a ⋅ ( b ⋅ c ) .

ii) (∀ a, b ∈ ℤm ) a ⋅ b = a ⋅ b = b ⋅ a = b ⋅ a .

iii) 1 ∈ ℤ m satisfaz a ⋅1 = a = 1⋅ a, ou seja, que a ⋅ 1 = 1 ⋅ a = a , ∀a ∈ℤ m . Vejamos que vale a unicidade: Seja b ∈ ℤm tal que a ⋅ b = a , ∀a ∈ℤ m . Em particular, para a = 1 , teremos que 1 ⋅ b = 1 , ou seja , que b = 1 . iv) (∀ a, b, c ∈ ℤm ), a ⋅ (b + c ) = a ⋅ (b+ c ) = a ⋅ b+ a ⋅ c ) = a ⋅ b + a ⋅ c = a ⋅ b + a ⋅ c . A demonstração de (b + c ) ⋅ a = b ⋅ a + c ⋅ a é análoga.

■ Em ℤ , vimos que se a·b = 0, então a = 0 ou b = 0. Em ℤ m essa propriedade pode não ser válida, dependendo do valor de m. Observe que em ℤ 6 temos que 2 ⋅ 3 = 6 = 0 mas, 2 ≠ 0 e 3 ≠ 0.

DEFINIÇÃO 9.3.4 Um elemento não nulo a ∈ ℤ m é denominado “divisor de zero” se existe b ∈ ℤ m , b ≠ 0 , tal que a ⋅ b = 0 .

PROPOSIÇÃO 9.3.5. Um elemento a ∈ ℤ m é divisor do zero mdc (a, m) ≠ 1.

se, e somente se,

Demonstração: Seja a um divisor do zero , seja b ∈ ℤ m , b ≠ 0 , tal que a ⋅ b = 0 . Como a ⋅ b = a ⋅ b = 0 , temos que a·b ≡ 0 (mod m), isto é, m \ a·b .

Supondo, por

absurdo, que mdc (a, m) = 1, teremos que m\ b, de modo que, teremos que b = 0 , o que será uma contradição.

Reciprocamente, se mdc (a, m)= d ≠ 1, isto é mdc (a, m) = d > 1, devemos determinar um elemento b ∈ ℤ m , b ≠ 0 , tal que a ⋅ b = 0 . Seja m1 = m / d. Então 0 < m1 < m, pois d >1. Assim, m1 ≠ 0 . Agora, temos que a ⋅ m1 = a ⋅ (m / d ) = (a / d ) ⋅ m , ou seja, a ⋅ m1 = 0 , ou ainda, a ⋅ m1 = 0 . Assim, tomemos b = m1 .

■ PROPOSIÇÃO 9.3.6: ℤ m não contém divisores do zero se, e somente se, m é primo. Demonstração: (⟸) Se m é primo, seja a ∈ ℤ m , a ≠ 0 . Supondo, sem perda de generalidade que a ∈ {1, 2, ..., m – 1 }, então mdc(a, m) = 1. Logo, pela Proposição 9.3.5, a não é divisor do zero. Assim, ℤ m não contém divisores do zero. (⟹) Suponhamos, por absurdo, que m seja composto, ou seja que m = x·y para algum inteiro x, 1 < x < m, e para algum inteiro y, 1 < y < m. Temos, então, que

0 = m = x ⋅y , em que

x ≠ 0 e y ≠ 0 , uma contradição.

■ PROPOSIÇÃO 9.3.7 i) Em ℤ m a propriedade cancelativa da adição é válida. ii) Em ℤ m a propriedade cancelativa da multiplicação é válida se, e somente se, m é primo. Demonstração: Deixamos como exercício. Veja a Lista 15 de exercícios.

■ DEFINIÇÃO 9.3.5 Um elemento a ∈ ℤ m

é dito ser invertível, se existe b ∈ ℤ m tal que

a ⋅ b = b ⋅ a = 1 . Neste caso, b é dito ser o inverso de a .

OBSERVAÇÃO: 5) 0 ∈ ℤ m não é invertível, pois 0 ⋅ a = 0, ∀a ∈ ℤ m , e 0 ≠ 1. 6) Em

ℤm ,

1

e

− 1 = −1

( − 1).( − 1) = −1⋅ −1 = ( −1) ⋅ ( −1) = 1 .

são sempre invertíveis. De fato,

1. 1 = 1

e

EXEMPLOS: 3) Em ℤ 5 , 2 , 3 e 4 são, também, invertíveis. De fato, 2 ⋅ 3 = 3 ⋅ 2 = 6 = 1 e 4 ⋅ 4 = 16 = 1 . E mais, 2 e 3 são inversos um do outro e 4 é o seu próprio inverso. 4) Em ℤ 6 , 5 ⋅ 5 = 25 = 1 mas, 2 ⋅ x ≠ 1, ∀x ∈ ℤ 6 . [ Confirme isto!]. Assim, 5 é invertível, mas 2 não o é.

PROPOSIÇÃO 9.3.8 Seja a ∈ ℤ m , a ≠ 0 . Tem-se:

a é invertível se, e somente se, mdc (a, m) = 1. Demonstração: (⟹) Demonstremos a contrapositiva, ou seja, “Se mdc (a, m) ≠ 1, então

a não é invertível”. Se mdc (a, m) ≠ 1, então a é divisor do zero, de modo que existe b ∈ ℤ m , b ≠ 0 , tal que

a ⋅ b = 0 . Se a fosse invertível, existiria a ' tal que a ⋅ a ' = 1 . Assim, teríamos que b = b ⋅ 1 = b ⋅ (a ⋅ a ') = (b ⋅ a ) ⋅ a ' = (a ⋅ b ) ⋅ a ' = 0 ⋅ a ' = 0 o que seria uma contradição. Logo, a não é invertível. (⟸) Suponhamos que mdc (a, m) = 1, então vamos demonstrar que a é invertível. Se mdc (a, m) = 1, então o Teorema de Bèzout nos garante que existem inteiros x0 e

y 0 tais que ax0 + my 0 = 1. Assim, 1 = a ⋅ x0 + m ⋅ y 0 = a ⋅ x0 + m ⋅ y 0 = a ⋅ x0 + 0 ⋅ y 0 = a ⋅ x 0 , e temos que a é invertível. ■ OBSERVAÇÃO: 7) A demonstração da proposição anterior também sugere um método para determinarmos o inverso de um dado elemento. EXEMPLO: 5) Em ℤ 37 , calcule o inverso de 4 . Pelo algoritmo de Euclides (ou diretamente, por inspeção), podemos obter que 1 = (− 9 ) ·4 + 1·(37) . Logo, em ℤ 37 , temos que 4 ⋅ −9 = 1 . Então, o inverso de 4 é −9 = 28 .

COROLÁRIO. Seja p > 1 um inteiro primo. Então, todo elemento a ∈ ℤ p , a ≠ 0 , é invertível.

Demonstração: Se p > 1 um inteiro primo. Qualquer que seja a ∈ ℤ p , a ≠ 0 , podemos supor que a ∈ {1, 2, ..., p – 1}. Assim mdc(a, p) = 1. Logo, pela proposição acima, temos que a é invertível.

■

LISTA 15 DE EXERCÍCIOS

1. Demonstre que em ℤ m tem-se que: i) m ⋅ 0 = 0 . ii) ( − 1) ⋅ m = −m . iii) −( −m ) = m . iv) ( −m ) ⋅ n = −(m ⋅ n ) = m ⋅ ( −n ) v) ( −m ) ⋅ ( −n ) = m ⋅ n .

2. Demonstre a Proposição 9.3.7. 3. Construa as tábuas da adição e da multiplicação em ℤ 7 e ℤ 8 .

4. Em ℤ 20 determine: a) os menores representantes positivos de −10 e −6 . b) todos os divisores do zero.

5. Determine todos os divisores do zero e todos os elementos invertíveis em

ℤ8 .

Também, para cada a um divisor do zero , determine b ∈ ℤ 8 , b ≠ 0 , tal que a ⋅ b = 0 . Para cada elemento invertível, determine o seu inverso.

6. Repita o exercício anterior em ℤ19 e em ℤ 24 .

7. Demonstre: “Se a ∈ ℤ m , a ≠ 0 , então a é um divisor do zero ou é um elemento invertível”.

8. Demonstre o seguinte resultado: “Seja a é um inteiro tal que mdc (a, m) = 1. Seja b um inteiro.

Então, a equação a ⋅ X = b tem uma única solução em ℤ m ” .

9. Resolva, se possível, as seguintes equações em ℤ m (não se esqueça de determinar todas as possíveis soluções): a) 2 ⋅ X = 4 ; m = 7 ; b) 2 ⋅ X = 4 ; m = 10 ; c) 9 ⋅ X = 4 ; m = 12 ; d) 9 ⋅ X = 9 ; m = 12 ; e) 3 ⋅ X + 8 = 1 ; m = 11 ; f)

3 ⋅ X + 2 = 6x + 7 ; m = 8 ;

g) 4 ⋅ X + 5 + 6 ⋅ X + 2 = 3 ⋅ X + 9 ⋅ X ; m = 12. h) 4 ⋅ X + 5 + 6 ⋅ X + 2 = 3 ⋅ X + 9 ⋅ X ; m = 9. i)

42 ⋅ X + 28 = 3 ; m = 59

10. Resolva, se possível, as seguintes equações em ℤ m (não se esqueça de determinar todas as possíveis soluções): a) b) c) d) e) f)

X 2 = 1 ; m = 13 X 2 = 11 ; m = 13 X 2 = 12 ; m = 13 X 2 = 1 ; m = 15 X 2 = 4 ; m = 15 X 2 = 10 ; m = 15

11. Determine se 3 640 é invertível em ℤ 7 297 . Em caso afirmativo, determine o seu inverso.

12. Use a seguinte versão do Teorema de Fermat para resolver as equações que se seguem: “ Seja p um primo positivo e seja a ∈ ℤ p . Então a p = a .” a) (2 X + 3)5 + (3 X + 2) + 5 X = 0 em ℤ 5 . b) X 101 − 2 = 0 em ℤ11 . c) X 14 − 1 = 0 em ℤ 7 . ====================================================================