Divisibilidade e Aritmética Modular - Matemática Discreta

Divisibilidade e Aritmetica Modular QXD0008 Matematica Discreta Prof Lucas Ismaily ismailybfufcbr Universidade Federal do Ceara 1º semestre2024 Topicos desta aula Esta apresentacao Introduz os conceitos de divisibilidade e divisao inteira Discute propriedades da relacao de divisibilidade Inclui exemplos de aplicacao dos conceitos em demonstracoes Introduz conceitos de Aritmetica Modular Explora teoremas sobre congruˆencias modulares e propriedades das operacoes em uma aritmetica modular 2 Referˆencias para esta aula Secao 34 do livro Matematica Discreta e suas Aplicacoes Autor Kenneth H Rosen Sexta Edicao Secao 41 do livro Discrete Mathematics and Its Applications Author Kenneth H Rosen Seventh Edition English version 3 Introdução Divisibilidade Definição Dados inteiros a e b com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Quando a divide b representamos isso pela notação ab Quando a não divide b representamos isso pela notação ab Divisibilidade Definição Dados inteiros a e b com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Quando a divide b representamos isso pela notação ab Quando a não divide b representamos isso pela notação ab Exemplo 3 divide 6 pois 6 3 3 ou seja existe um inteiro c tal que 6 3 c Neste caso temos c 2 Definição Dados inteiros a e b com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Quando a divide b representamos isso pela notação ab Quando a não divide b representamos isso pela notação ab Exemplo 3 divide 6 pois 6 3 3 ou seja existe um inteiro c tal que 6 3 c Neste caso temos c 2 2 divide 30 pois 30 2 15 ou seja existe um inteiro c tal que 30 2c Neste caso temos d 15 4 divide 68 pois 68 4 17 ou seja existe um inteiro c tal que 68 4c Neste caso c 17 Definição Dados inteiros a e b com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Quando a divide b representamos isso pela notação ab Quando a não divide b representamos isso pela notação ab Exemplo 3 divide 6 pois 6 3 3 ou seja existe um inteiro c tal que 6 3 c Neste caso temos c 2 2 divide 30 pois 30 2 15 ou seja existe um inteiro c tal que 30 2c Neste caso temos d 15 4 divide 68 pois 68 4 17 ou seja existe um inteiro c tal que 68 4c Neste caso c 17 Definição Dados inteiros a e b com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Quando a divide b representamos isso pela notação ab Quando a não divide b representamos isso pela notação ab Divisibilidade Definição Dados inteiros a e b com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Quando a divide b representamos isso pela notação ab Quando a não divide b representamos isso pela notação ab Exemplo 3 não divide 16 pois não existe nenhum inteiro c tal que 16 3c Como verificar Divisibilidade Definição Dados inteiros a e b com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Quando a divide b representamos isso pela notação ab Quando a não divide b representamos isso pela notação ab Exemplo 3 não divide 16 pois não existe nenhum inteiro c tal que 16 3c Como verificar 1 Por absurdo suponha que existe c ℤ tal que 16 3c 2 Observe que 35 15 e que 36 18 3 Como 15 16 18 temos que 35 3c 36 Divisibilidade Definição Dados inteiros a e b com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Quando a divide b representamos isso pela notação ab Quando a não divide b representamos isso pela notação ab Exemplo 3 não divide 16 pois não existe nenhum inteiro c tal que 16 3c Como verificar 1 Por absurdo suponha que existe c ℤ tal que 16 3c 2 Observe que 35 15 e que 36 18 3 Como 15 16 18 temos que 35 3c 36 4 Dividindo todos os termos da inequação por 3 obtemos 5 c 6 5 Absurdo pois não existem inteiros entre 5 e 6 6 Concluímos que não existe c ℤ tal que 16 3c Divisibilidade Proposicao 71 Sejam a e b numeros inteiros com a 0 Entao a divide b se e somente se b a e um inteiro aba 0 ab b a Z Demonstracao Sejam ab inteiros quaisquer com a 0 Instanciacao Suponha que a divide b Hipotese da PD Pela definicao de divisibilidade existe um inteiro c tal que b ac Como a 0 obtemos b a c e portanto que b a e um inteiro Suponha que b a e um inteiro Hipotese da PD Isso implica b a c para c Z Multiplicando ambos os lados da igualdade por a obtemos b ac Pela definicao de divisibilidade temos que a divide b 7 Divisibilidade Proposicao 71 Sejam a e b numeros inteiros com a 0 Entao a divide b se e somente se b a e um inteiro aba 0 ab b a Z Demonstracao Sejam ab inteiros quaisquer com a 0 Instanciacao Suponha que a divide b Hipotese da PD Pela definicao de divisibilidade existe um inteiro c tal que b ac Como a 0 obtemos b a c e portanto que b a e um inteiro Suponha que b a e um inteiro Hipotese da PD Isso implica b a c para c Z Multiplicando ambos os lados da igualdade por a obtemos b ac Pela definicao de divisibilidade temos que a divide b 7 Divisibilidade Proposicao 71 Sejam a e b numeros inteiros com a 0 Entao a divide b se e somente se b a e um inteiro aba 0 ab b a Z Demonstracao Sejam ab inteiros quaisquer com a 0 Instanciacao Suponha que a divide b Hipotese da PD Pela definicao de divisibilidade existe um inteiro c tal que b ac Como a 0 obtemos b a c e portanto que b a e um inteiro Suponha que b a e um inteiro Hipotese da PD Isso implica b a c para c Z Multiplicando ambos os lados da igualdade por a obtemos b ac Pela definicao de divisibilidade temos que a divide b 7 Divisibilidade Proposicao 71 Sejam a e b numeros inteiros com a 0 Entao a divide b se e somente se b a e um inteiro aba 0 ab b a Z Demonstracao Sejam ab inteiros quaisquer com a 0 Instanciacao Suponha que a divide b Hipotese da PD Pela definicao de divisibilidade existe um inteiro c tal que b ac Como a 0 obtemos b a c e portanto que b a e um inteiro Suponha que b a e um inteiro Hipotese da PD Isso implica b a c para c Z Multiplicando ambos os lados da igualdade por a obtemos b ac Pela definicao de divisibilidade temos que a divide b 7 Divisibilidade Proposicao 71 Sejam a e b numeros inteiros com a 0 Entao a divide b se e somente se b a e um inteiro Exemplos 2 divide 30 pois 30 2 15 da mesma forma 30 2 e um inteiro pois 30 2 15 3 nao divide 16 pois nao existe c Z tal que 6 3c da mesma forma 16 3 nao e um inteiro pois 16 3 5 33333 8 Divisibilidade Proposicao 71 Sejam a e b numeros inteiros com a 0 Entao a divide b se e somente se b a e um inteiro Exemplos 2 divide 30 pois 30 2 15 da mesma forma 30 2 e um inteiro pois 30 2 15 3 nao divide 16 pois nao existe c Z tal que 6 3c da mesma forma 16 3 nao e um inteiro pois 16 3 5 33333 8 Divisibilidade Terminologia Fator Divisor Multiplo Quando a divide b dizemos de forma sinˆonima que a e um fator de b a e um divisor de b b e um multiplo de a b e divisıvel por a Exemplo Vimos que 3 divide 6 Da mesma forma podemos dizer que 3 e fator de 6 que 3 e divisor de 6 que 6 e multiplo de 3 e que 6 e divisıvel por 3 Como 3 nao divide 16 podemos dizer que 3 nao e fator de 16 que 3 nao e divisor de 16 que 16 nao e multiplo de 3 e que 16 nao e divisıvel por 3 9 Divisibilidade Terminologia Fator Divisor Multiplo Quando a divide b dizemos de forma sinˆonima que a e um fator de b a e um divisor de b b e um multiplo de a b e divisıvel por a Exemplo Vimos que 3 divide 6 Da mesma forma podemos dizer que 3 e fator de 6 que 3 e divisor de 6 que 6 e multiplo de 3 e que 6 e divisıvel por 3 Como 3 nao divide 16 podemos dizer que 3 nao e fator de 16 que 3 nao e divisor de 16 que 16 nao e multiplo de 3 e que 16 nao e divisıvel por 3 9 Divisibilidade Terminologia Fator Divisor Multiplo Quando a divide b dizemos de forma sinˆonima que a e um fator de b a e um divisor de b b e um multiplo de a b e divisıvel por a Exemplo Vimos que 3 divide 6 Da mesma forma podemos dizer que 3 e fator de 6 que 3 e divisor de 6 que 6 e multiplo de 3 e que 6 e divisıvel por 3 Como 3 nao divide 16 podemos dizer que 3 nao e fator de 16 que 3 nao e divisor de 16 que 16 nao e multiplo de 3 e que 16 nao e divisıvel por 3 9 Divisibilidade e números pares Divisibilidade e numeros pares Definicao numero par Seja n um inteiro Dizemos que n e par se e somente se existe um inteiro k tal que n 2k Compare com a definicao de divisibilidade Definicao divisibilidade Sejam a e b numeros inteiros com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Podemos entao reescrever Definicao numero par Alternativa 2 Seja n um inteiro Dizemos que n e par se e somente se 2 divide n 11 Divisibilidade e numeros pares Definicao numero par Seja n um inteiro Dizemos que n e par se e somente se existe um inteiro k tal que n 2k Compare com a definicao de divisibilidade Definicao divisibilidade Sejam a e b numeros inteiros com a 0 dizemos que a divide b se e somente se existe um inteiro c tal que b ac Podemos entao reescrever Definicao numero par Alternativa 2 Seja n um inteiro Dizemos que n e par se e somente se 2 divide n 11 Par e ımpar Proposicao 72 Nenhum inteiro e ao mesmo tempo par e ımpar Reexpressa na forma seentao essa proposicao e se x e um inteiro entao x nao pode ser simultaneamente par e ımpar Demonstracao Seja x um inteiro Suponha por contradicao que x seja par e ımpar Como x e par sabemos que 2x isto e existe um inteiro a de modo que x 2a Como x e ımpar sabemos que existe um inteiro b de modo que x 2b 1 Portanto 2a 2b 1 Dividindo ambos os termos por 2 obtemos a b 1 2 de forma que a b 1 2 Note que a b e um inteiro pois a e b o sao mas 1 2 nao e inteiro Logo x nao e ao mesmo tempo par e ımpar 12 Par e ımpar Proposicao 72 Nenhum inteiro e ao mesmo tempo par e ımpar Reexpressa na forma seentao essa proposicao e se x e um inteiro entao x nao pode ser simultaneamente par e ımpar Demonstracao Seja x um inteiro Suponha por contradicao que x seja par e ımpar Como x e par sabemos que 2x isto e existe um inteiro a de modo que x 2a Como x e ımpar sabemos que existe um inteiro b de modo que x 2b 1 Portanto 2a 2b 1 Dividindo ambos os termos por 2 obtemos a b 1 2 de forma que a b 1 2 Note que a b e um inteiro pois a e b o sao mas 1 2 nao e inteiro Logo x nao e ao mesmo tempo par e ımpar 12 Par e ımpar Proposicao 72 Nenhum inteiro e ao mesmo tempo par e ımpar Reexpressa na forma seentao essa proposicao e se x e um inteiro entao x nao pode ser simultaneamente par e ımpar Demonstracao Seja x um inteiro Suponha por contradicao que x seja par e ımpar Como x e par sabemos que 2x isto e existe um inteiro a de modo que x 2a Como x e ımpar sabemos que existe um inteiro b de modo que x 2b 1 Portanto 2a 2b 1 Dividindo ambos os termos por 2 obtemos a b 1 2 de forma que a b 1 2 Note que a b e um inteiro pois a e b o sao mas 1 2 nao e inteiro Logo x nao e ao mesmo tempo par e ımpar 12 Par e ımpar Proposicao 72 Nenhum inteiro e ao mesmo tempo par e ımpar Reexpressa na forma seentao essa proposicao e se x e um inteiro entao x nao pode ser simultaneamente par e ımpar Demonstracao Seja x um inteiro Suponha por contradicao que x seja par e ımpar Como x e par sabemos que 2x isto e existe um inteiro a de modo que x 2a Como x e ımpar sabemos que existe um inteiro b de modo que x 2b 1 Portanto 2a 2b 1 Dividindo ambos os termos por 2 obtemos a b 1 2 de forma que a b 1 2 Note que a b e um inteiro pois a e b o sao mas 1 2 nao e inteiro Logo x nao e ao mesmo tempo par e ımpar 12 Par e ımpar Proposicao 72 Nenhum inteiro e ao mesmo tempo par e ımpar Reexpressa na forma seentao essa proposicao e se x e um inteiro entao x nao pode ser simultaneamente par e ımpar Demonstracao Seja x um inteiro Suponha por contradicao que x seja par e ımpar Como x e par sabemos que 2x isto e existe um inteiro a de modo que x 2a Como x e ımpar sabemos que existe um inteiro b de modo que x 2b 1 Portanto 2a 2b 1 Dividindo ambos os termos por 2 obtemos a b 1 2 de forma que a b 1 2 Note que a b e um inteiro pois a e b o sao mas 1 2 nao e inteiro Logo x nao e ao mesmo tempo par e ımpar 12 Par e ımpar Proposicao 72 Nenhum inteiro e ao mesmo tempo par e ımpar Reexpressa na forma seentao essa proposicao e se x e um inteiro entao x nao pode ser simultaneamente par e ımpar Demonstracao Seja x um inteiro Suponha por contradicao que x seja par e ımpar Como x e par sabemos que 2x isto e existe um inteiro a de modo que x 2a Como x e ımpar sabemos que existe um inteiro b de modo que x 2b 1 Portanto 2a 2b 1 Dividindo ambos os termos por 2 obtemos a b 1 2 de forma que a b 1 2 Note que a b e um inteiro pois a e b o sao mas 1 2 nao e inteiro Logo x nao e ao mesmo tempo par e ımpar 12 Propriedades da relacao de divisibilidade 13 Propriedades da divisibilidade Teorema 73 Sejam a b e c numeros inteiros com a 0 Entao 1 Se ab e ac entao ab c 2 Se ab entao abc para todo c inteiro 3 Se ab e bc entao ac Demonstracao Prova do condicional 1 Sejam a b e c inteiros quaisquer com a 0 Instanciacao universalSuponha que ab e ac Hipotese da PD Pela definicao de divisibilidade existem inteiros s e t tais que b as e c at Portanto b c as at as t Igualdades Distributividade Como s e t sao inteiros s t e inteiro Portanto ab c Divisibilidade Condicional 2 Deixado como exercıcio Condicional 3 Provado em aulas passadas 14 Propriedades da divisibilidade Teorema 73 Sejam a b e c numeros inteiros com a 0 Entao 1 Se ab e ac entao ab c 2 Se ab entao abc para todo c inteiro 3 Se ab e bc entao ac Demonstracao Prova do condicional 1 Sejam a b e c inteiros quaisquer com a 0 Instanciacao universal Suponha que ab e ac Hipotese da PD Pela definicao de divisibilidade existem inteiros s e t tais que b as e c at Portanto b c as at as t Igualdades Distributividade Como s e t sao inteiros s t e inteiro Portanto ab c Divisibilidade Condicional 2 Deixado como exercıcio Condicional 3 Provado em aulas passadas 14 Propriedades da divisibilidade Teorema 73 Sejam a b e c numeros inteiros com a 0 Entao 1 Se ab e ac entao ab c 2 Se ab entao abc para todo c inteiro 3 Se ab e bc entao ac Demonstracao Prova do condicional 1 Sejam a b e c inteiros quaisquer com a 0 Instanciacao universalSuponha que ab e ac Hipotese da PD Pela definicao de divisibilidade existem inteiros s e t tais que b as e c at Portanto b c as at as t Igualdades Distributividade Como s e t sao inteiros s t e inteiro Portanto ab c Divisibilidade Condicional 2 Deixado como exercıcio Condicional 3 Provado em aulas passadas 14 Propriedades da divisibilidade Teorema 73 Sejam a b e c numeros inteiros com a 0 Entao 1 Se ab e ac entao ab c 2 Se ab entao abc para todo c inteiro 3 Se ab e bc entao ac Demonstracao Prova do condicional 1 Sejam a b e c inteiros quaisquer com a 0 Instanciacao universalSuponha que ab e ac Hipotese da PD Pela definicao de divisibilidade existem inteiros s e t tais que b as e c at Portanto b c as at as t Igualdades Distributividade Como s e t sao inteiros s t e inteiro Portanto ab c Divisibilidade Condicional 2 Deixado como exercıcio Condicional 3 Provado em aulas passadas 14 Propriedades da divisibilidade Teorema 73 Sejam a b e c numeros inteiros com a 0 Entao 1 Se ab e ac entao ab c 2 Se ab entao abc para todo c inteiro 3 Se ab e bc entao ac Demonstracao Prova do condicional 1 Sejam a b e c inteiros quaisquer com a 0 Instanciacao universalSuponha que ab e ac Hipotese da PD Pela definicao de divisibilidade existem inteiros s e t tais que b as e c at Portanto b c as at as t Igualdades Distributividade Como s e t sao inteiros s t e inteiro Portanto ab c Divisibilidade Condicional 2 Deixado como exercıcio Condicional 3 Provado em aulas passadas 14 Propriedades da divisibilidade Teorema 73 Sejam a b e c numeros inteiros com a 0 Entao 1 Se ab e ac entao ab c 2 Se ab entao abc para todo c inteiro 3 Se ab e bc entao ac Demonstracao Prova do condicional 1 Sejam a b e c inteiros quaisquer com a 0 Instanciacao universalSuponha que ab e ac Hipotese da PD Pela definicao de divisibilidade existem inteiros s e t tais que b as e c at Portanto b c as at as t Igualdades Distributividade Como s e t sao inteiros s t e inteiro Portanto ab c Divisibilidade Condicional 2 Deixado como exercıcio Condicional 3 Provado em aulas passadas 14 Propriedades da divisibilidade Teorema 73 Sejam a b e c numeros inteiros com a 0 Entao 1 Se ab e ac entao ab c 2 Se ab entao abc para todo c inteiro 3 Se ab e bc entao ac Demonstracao Prova do condicional 1 Sejam a b e c inteiros quaisquer com a 0 Instanciacao universalSuponha que ab e ac Hipotese da PD Pela definicao de divisibilidade existem inteiros s e t tais que b as e c at Portanto b c as at as t Igualdades Distributividade Como s e t sao inteiros s t e inteiro Portanto ab c Divisibilidade Condicional 2 Deixado como exercıcio Condicional 3 Provado em aulas passadas 14 Propriedades da divisibilidade Teorema 73 Sejam a b e c numeros inteiros com a 0 Entao 1 Se ab e ac entao ab c 2 Se ab entao abc para todo c inteiro 3 Se ab e bc entao ac Corolario 74 Se a b e c sao inteiros tais que a 0 ab e ac entao amb nc para quaisqer m e n inteiros Demonstracao Pela afirmacao 2 do teorema 72 vemos que amb para todo inteiro m e que anc para todo inteiro n Daı podemos usar a afirmacao 1 para concluir que amb nc 15 Propriedades da divisibilidade Teorema 73 Sejam a b e c numeros inteiros com a 0 Entao 1 Se ab e ac entao ab c 2 Se ab entao abc para todo c inteiro 3 Se ab e bc entao ac Corolario 74 Se a b e c sao inteiros tais que a 0 ab e ac entao amb nc para quaisqer m e n inteiros Demonstracao Pela afirmacao 2 do teorema 72 vemos que amb para todo inteiro m e que anc para todo inteiro n Daı podemos usar a afirmacao 1 para concluir que amb nc 15 Propriedades da divisibilidade Teorema 73 Sejam a b e c numeros inteiros com a 0 Entao 1 Se ab e ac entao ab c 2 Se ab entao abc para todo c inteiro 3 Se ab e bc entao ac Corolario 74 Se a b e c sao inteiros tais que a 0 ab e ac entao amb nc para quaisqer m e n inteiros Demonstracao Pela afirmacao 2 do teorema 72 vemos que amb para todo inteiro m e que anc para todo inteiro n Daı podemos usar a afirmacao 1 para concluir que amb nc 15 Propriedades da divisibilidade Teorema 73 Sejam a b e c numeros inteiros com a 0 Entao 1 Se ab e ac entao ab c 2 Se ab entao abc para todo c inteiro 3 Se ab e bc entao ac Corolario 74 Se a b e c sao inteiros tais que a 0 ab e ac entao amb nc para quaisqer m e n inteiros Demonstracao Pela afirmacao 2 do teorema 72 vemos que amb para todo inteiro m e que anc para todo inteiro n Daı podemos usar a afirmacao 1 para concluir que amb nc 15 Algoritmo da divisão Divisao Teorema 75 Algoritmo da divisao Seja n um inteiro qualquer e d um inteiro positivo Entao existe um unico par de inteiros q e r com 0 r d tais que n dq r Este teorema trata da divisao de inteiros n d r q Numa divisao como esta acima n e chamado dividendo d e chamado divisor q e chamado quociente r e chamado resto 17 Divisao Teorema 75 Algoritmo da divisao Seja n um inteiro qualquer e d um inteiro positivo Entao existe um unico par de inteiros q e r com 0 r d tais que n dq r Este teorema trata da divisao de inteiros n d r q Numa divisao como esta acima n e chamado dividendo d e chamado divisor q e chamado quociente r e chamado resto 17 Divisao Teorema 75 Algoritmo da divisao Seja n um inteiro qualquer e d um inteiro positivo Entao existe um unico par de inteiros q e r com 0 r d tais que n dq r Observacao A condicao 0 r d e fundamental pois sem ela existirao infinitos pares q r tais que n dq r Exemplo Considere n 10 e d 3 Se nao restringirmos r teremos 10 33 19 10 32 16 10 31 13 10 3 0 10 10 3 1 7 10 3 2 4 10 3 3 1 10 3 4 2 10 3 5 5 10 3 6 8 mas havera apenas um caso em que 0 r 3 18 Divisao Teorema 75 Algoritmo da divisao Seja n um inteiro qualquer e d um inteiro positivo Entao existe um unico par de inteiros q e r com 0 r d tais que n dq r Observacao A condicao 0 r d e fundamental pois sem ela existirao infinitos pares q r tais que n dq r Exemplo Considere n 10 e d 3 Se nao restringirmos r teremos 10 33 19 10 32 16 10 31 13 10 3 0 10 10 3 1 7 10 3 2 4 10 3 3 1 10 3 4 2 10 3 5 5 10 3 6 8 mas havera apenas um caso em que 0 r 3 18 Divisao Teorema 75 Algoritmo da divisao Seja n um inteiro qualquer e d um inteiro positivo Entao existe um unico par de inteiros q e r com 0 r d tais que n dq r Observacao A condicao 0 r d e fundamental pois sem ela existirao infinitos pares q r tais que n dq r Exemplo Considere n 10 e d 3 Se nao restringirmos r teremos 10 33 19 10 32 16 10 31 13 10 3 0 10 10 3 1 7 10 3 2 4 10 3 3 1 10 3 4 2 10 3 5 5 10 3 6 8 mas havera apenas um caso em que 0 r 3 18 Divisao Teorema 75 Algoritmo da divisao Seja n um inteiro qualquer e d um inteiro positivo Entao existe um unico par de inteiros q e r com 0 r d tais que n dq r Observacao A condicao 0 r d e fundamental pois sem ela existirao infinitos pares q r tais que n dq r Exemplo Considere n 10 e d 3 Se nao restringirmos r teremos 10 33 19 10 32 16 10 31 13 10 3 0 10 10 3 1 7 10 3 2 4 10 3 3 1 10 3 4 2 10 3 5 5 10 3 6 8 mas havera apenas um caso em que 0 r 3 18 Pares e ımpares Teorema 76 Todo inteiro e par ou ımpar mas nao os dois Demonstracao Provamos anteriormente que nenhum inteiro pode ser simultaneamente par e ımpar Com isso resta mostrar que todo inteiro e um ou outro Vamos usar o Teorema do Algoritmo da Divisao para mostrar isso Seja n qualquer inteiro Pelo Teorema 75 podemos encontrar os inteiros q e r de forma que n 2q r em que 0 r 2 Observe que se r 0 entao n e par e se r 1 entao n e ımpar 19 Pares e ımpares Teorema 76 Todo inteiro e par ou ımpar mas nao os dois Demonstracao Provamos anteriormente que nenhum inteiro pode ser simultaneamente par e ımpar Com isso resta mostrar que todo inteiro e um ou outro Vamos usar o Teorema do Algoritmo da Divisao para mostrar isso Seja n qualquer inteiro Pelo Teorema 75 podemos encontrar os inteiros q e r de forma que n 2q r em que 0 r 2 Observe que se r 0 entao n e par e se r 1 entao n e ımpar 19 Pares e ımpares Teorema 76 Todo inteiro e par ou ımpar mas nao os dois Demonstracao Provamos anteriormente que nenhum inteiro pode ser simultaneamente par e ımpar Com isso resta mostrar que todo inteiro e um ou outro Vamos usar o Teorema do Algoritmo da Divisao para mostrar isso Seja n qualquer inteiro Pelo Teorema 75 podemos encontrar os inteiros q e r de forma que n 2q r em que 0 r 2 Observe que se r 0 entao n e par e se r 1 entao n e ımpar 19 Pares e ımpares Teorema 76 Todo inteiro e par ou ımpar mas nao os dois Demonstracao Provamos anteriormente que nenhum inteiro pode ser simultaneamente par e ımpar Com isso resta mostrar que todo inteiro e um ou outro Vamos usar o Teorema do Algoritmo da Divisao para mostrar isso Seja n qualquer inteiro Pelo Teorema 75 podemos encontrar os inteiros q e r de forma que n 2q r em que 0 r 2 Observe que se r 0 entao n e par e se r 1 entao n e ımpar 19 Operacoes div e mod Definicao Sejam n d q r inteiros tais que d 0 e n dq r com 0 r d definimos as funcoes div e mod tais que n div d q divisao inteirasem resto n mod d r moduloresto da divisao 20 Operacoes div e mod Na divisao de 110 por 9 temos 110 9 9 12 20 18 2 Isso nos da que 110 9 12 2 110 div 9 12 110 mod 9 2 21 Operacoes div e mod Na divisao de 110 por 9 temos 110 9 9 13 20 27 7 Isso nos da que 110 9 13 7 110 div 9 13 110 mod 9 7 Por que o quociente nao e 12 Como 9 12 108 se usassemos q 12 na expressao 110 9q r terıamos r 2 110 9 12 r 110 108 r 110 108 r 110 108 r r 2 Lembrese que precisamos satisfazer 0 r 9 22 Operacoes div e mod Na divisao de 110 por 9 temos 110 9 9 13 20 27 7 Isso nos da que 110 9 13 7 110 div 9 13 110 mod 9 7 Por que o quociente nao e 12 Como 9 12 108 se usassemos q 12 na expressao 110 9q r terıamos r 2 110 9 12 r 110 108 r 110 108 r 110 108 r r 2 Lembrese que precisamos satisfazer 0 r 9 22 Operacoes div e mod Na divisao de 110 por 9 temos 110 9 9 13 20 27 7 Isso nos da que 110 9 13 7 110 div 9 13 110 mod 9 7 Por que o quociente nao e 12 Como 9 12 108 se usassemos q 12 na expressao 110 9q r terıamos r 2 110 9 12 r 110 108 r 110 108 r 110 108 r r 2 Lembrese que precisamos satisfazer 0 r 9 22 Operacoes div e mod Na divisao de 110 por 9 temos 110 9 9 13 20 27 7 Isso nos da que 110 9 13 7 110 div 9 13 110 mod 9 7 Por que o quociente nao e 12 Como 9 12 108 se usassemos q 12 na expressao 110 9q r terıamos r 2 110 9 12 r 110 108 r 110 108 r 110 108 r r 2 Lembrese que precisamos satisfazer 0 r 9 22 Operacoes div e mod Na divisao de 110 por 9 temos 110 9 9 13 20 27 7 Isso nos da que 110 9 13 7 110 div 9 13 110 mod 9 7 Por que o quociente nao e 12 Como 9 12 108 se usassemos q 12 na expressao 110 9q r terıamos r 2 110 9 12 r 110 108 r 110 108 r 110 108 r r 2 Lembrese que precisamos satisfazer 0 r 9 22 Relacao entre divisibilidade e o Algoritmo da Divisao 23 Divisibilidade e Algoritmo da Divisao Teorema 75 Algoritmo da divisao Seja n um inteiro qualquer e d um inteiro positivo Entao existe um unico par de inteiros q e r com 0 r d tais que n dq r O que ocorre quando temos r 0 Isto so e possıvel para alguns valores de n e d A expressao n dq r tornase simplesmente n dq Como q e inteiro n dq nos diz que d divide n 24 Divisibilidade e Algoritmo da Divisao Teorema 77 Sejam a b inteiros com a 0 temos que a divide b se e somente se b mod a 0 Demonstracao Sejam a b inteiros com a 0 Suponha que ab Logo existe um inteiro c tal que b ac definicao de divisibilidade Podemos reescrever a igualdade como b ac 0 Elemento neutro da soma Neste ponto o par de inteiros c 0 satisfaz os requisitos do algoritmo da divisao Portanto na divisao de b por a temos b div a c e b mod a 0 25 Divisibilidade e Algoritmo da Divisao Teorema 77 Sejam a b inteiros com a 0 temos que a divide b se e somente se b mod a 0 Demonstracao Sejam a b inteiros com a 0 Suponha que ab Logo existe um inteiro c tal que b ac definicao de divisibilidade Podemos reescrever a igualdade como b ac 0 Elemento neutro da soma Neste ponto o par de inteiros c 0 satisfaz os requisitos do algoritmo da divisao Portanto na divisao de b por a temos b div a c e b mod a 0 25 Divisibilidade e Algoritmo da Divisao Teorema 77 Sejam a b inteiros com a 0 temos que a divide b se e somente se b mod a 0 Demonstracao Sejam a b inteiros com a 0 Suponha que ab Logo existe um inteiro c tal que b ac definicao de divisibilidade Podemos reescrever a igualdade como b ac 0 Elemento neutro da soma Neste ponto o par de inteiros c 0 satisfaz os requisitos do algoritmo da divisao Portanto na divisao de b por a temos b div a c e b mod a 0 25 Divisibilidade e Algoritmo da Divisao Teorema 77 Sejam a b inteiros com a 0 temos que a divide b se e somente se b mod a 0 Demonstracao Sejam a b inteiros com a 0 Suponha que ab Logo existe um inteiro c tal que b ac definicao de divisibilidade Podemos reescrever a igualdade como b ac 0 Elemento neutro da soma Neste ponto o par de inteiros c 0 satisfaz os requisitos do algoritmo da divisao Portanto na divisao de b por a temos b div a c e b mod a 0 25 Divisibilidade e Algoritmo da Divisao Teorema 77 Sejam a b inteiros com a 0 temos que a divide b se e somente se b mod a 0 Demonstracao Sejam a b inteiros com a 0 Suponha que ab Logo existe um inteiro c tal que b ac definicao de divisibilidade Podemos reescrever a igualdade como b ac 0 Elemento neutro da soma Neste ponto o par de inteiros c 0 satisfaz os requisitos do algoritmo da divisao Portanto na divisao de b por a temos b div a c e b mod a 0 25 Divisibilidade e Algoritmo da Divisao Teorema 77 Sejam a b inteiros com a 0 temos que a divide b se e somente se b mod a 0 Demonstracao Sejam a b inteiros com a 0 Suponha que ab Logo existe um inteiro c tal que b ac definicao de divisibilidade Podemos reescrever a igualdade como b ac 0 Elemento neutro da soma Neste ponto o par de inteiros c 0 satisfaz os requisitos do algoritmo da divisao Portanto na divisao de b por a temos b div a c e b mod a 0 25 Divisibilidade e Algoritmo da Divisao Teorema 77 Sejam a b inteiros com a 0 temos que a divide b se e somente se b mod a 0 Demonstracao Sejam a b inteiros com a 0 Suponha que b mod a 0 Seja b div a c onde c e um inteiro Pelo algoritmo da divisao temos que b ac 0 Todo numero somado com zero resulta no proprio numero Logo b ac tal que a 0 e c e um inteiro Pela definicao de divisibilidade temos que a divide b 26 Divisibilidade e Algoritmo da Divisao Teorema 77 Sejam a b inteiros com a 0 temos que a divide b se e somente se b mod a 0 Demonstracao Sejam a b inteiros com a 0 Suponha que b mod a 0 Seja b div a c onde c e um inteiro Pelo algoritmo da divisao temos que b ac 0 Todo numero somado com zero resulta no proprio numero Logo b ac tal que a 0 e c e um inteiro Pela definicao de divisibilidade temos que a divide b 26 Divisibilidade e Algoritmo da Divisao Teorema 77 Sejam a b inteiros com a 0 temos que a divide b se e somente se b mod a 0 Demonstracao Sejam a b inteiros com a 0 Suponha que b mod a 0 Seja b div a c onde c e um inteiro Pelo algoritmo da divisao temos que b ac 0 Todo numero somado com zero resulta no proprio numero Logo b ac tal que a 0 e c e um inteiro Pela definicao de divisibilidade temos que a divide b 26 Divisibilidade e Algoritmo da Divisao Teorema 77 Sejam a b inteiros com a 0 temos que a divide b se e somente se b mod a 0 Demonstracao Sejam a b inteiros com a 0 Suponha que b mod a 0 Seja b div a c onde c e um inteiro Pelo algoritmo da divisao temos que b ac 0 Todo numero somado com zero resulta no proprio numero Logo b ac tal que a 0 e c e um inteiro Pela definicao de divisibilidade temos que a divide b 26 Divisibilidade e Algoritmo da Divisao Teorema 77 Sejam a b inteiros com a 0 temos que a divide b se e somente se b mod a 0 Demonstracao Sejam a b inteiros com a 0 Suponha que b mod a 0 Seja b div a c onde c e um inteiro Pelo algoritmo da divisao temos que b ac 0 Todo numero somado com zero resulta no proprio numero Logo b ac tal que a 0 e c e um inteiro Pela definicao de divisibilidade temos que a divide b 26 Aritmética Modular Congruˆencia modular Definicao Congruˆencia modulo m Dados dois inteiros a e b e um inteiro positivo m dizemos que a e congruente a b modulo m se e somente se ma b Exemplos Positivos 370 114 256 que e divisıvel por 256 pois 256 mod 256 0 Logo 370 e congruente a 114 modulo 256 370 142 512 que e divisıvel por 256 pois 512 mod 256 0 Logo 370 e congruente a 142 modulo 256 142 114 256 que e divisıvel por 256 pois 256 mod 256 0 Logo 142 e congruente a 114 modulo 256 28 Congruˆencia modular Definicao Congruˆencia modulo m Dados dois inteiros a e b e um inteiro positivo m dizemos que a e congruente a b modulo m se e somente se ma b Exemplos Positivos 370 114 256 que e divisıvel por 256 pois 256 mod 256 0 Logo 370 e congruente a 114 modulo 256 370 142 512 que e divisıvel por 256 pois 512 mod 256 0 Logo 370 e congruente a 142 modulo 256 142 114 256 que e divisıvel por 256 pois 256 mod 256 0 Logo 142 e congruente a 114 modulo 256 28 Congruˆencia modular Definicao Congruˆencia modulo m Dados dois inteiros a e b e um inteiro positivo m dizemos que a e congruente a b modulo m se e somente se ma b Exemplos Positivos 370 114 256 que e divisıvel por 256 pois 256 mod 256 0 Logo 370 e congruente a 114 modulo 256 370 142 512 que e divisıvel por 256 pois 512 mod 256 0 Logo 370 e congruente a 142 modulo 256 142 114 256 que e divisıvel por 256 pois 256 mod 256 0 Logo 142 e congruente a 114 modulo 256 28 Congruˆencia modular Definicao Congruˆencia modulo m Dados dois inteiros a e b e um inteiro positivo m dizemos que a e congruente a b modulo m se e somente se ma b Exemplos Positivos 370 114 256 que e divisıvel por 256 pois 256 mod 256 0 Logo 370 e congruente a 114 modulo 256 370 142 512 que e divisıvel por 256 pois 512 mod 256 0 Logo 370 e congruente a 142 modulo 256 142 114 256 que e divisıvel por 256 pois 256 mod 256 0 Logo 142 e congruente a 114 modulo 256 28 Congruˆencia modular Definicao Congruˆencia modulo m Dados dois inteiros a e b e um inteiro positivo m dizemos que a e congruente a b modulo m se e somente se ma b Exemplos Negativos 400 114 286 que nao e divisıvel por 256 pois 286 mod 256 30 ou seja 400 nao e congruente a 11 modulo 256 370 400 30 que nao e divisıvel por 256 pois 30 mod 256 226 ou seja 370 nao e congruente a 400 modulo 256 29 Congruˆencia modular Definicao Congruˆencia modulo m Dados dois inteiros a e b e um inteiro positivo m dizemos que a e congruente a b modulo m se e somente se ma b Exemplos Negativos 400 114 286 que nao e divisıvel por 256 pois 286 mod 256 30 ou seja 400 nao e congruente a 11 modulo 256 370 400 30 que nao e divisıvel por 256 pois 30 mod 256 226 ou seja 370 nao e congruente a 400 modulo 256 29 Congruˆencia modular Definicao Congruˆencia modulo m Dados dois inteiros a e b e um inteiro positivo m dizemos que a e congruente a b modulo m se e somente se ma b Exemplos Negativos 400 114 286 que nao e divisıvel por 256 pois 286 mod 256 30 ou seja 400 nao e congruente a 11 modulo 256 370 400 30 que nao e divisıvel por 256 pois 30 mod 256 226 ou seja 370 nao e congruente a 400 modulo 256 29 Congruˆencia modular Definicao Congruˆencia modulo m Dados dois inteiros a e b e um inteiro positivo m dizemos que a e congruente a b modulo m se e somente se ma b Notacao Escrevese a b mod m para dizer que a e congruente a b modulo m Escrevese a b mod m para dizer que a nao e congruente a b modulo m Exemplo 370 114 mod 256 370 142 mod 256 142 114 mod 256 400 114 mod 256 370 400 mod 256 30 Congruˆencia modular Definicao Congruˆencia modulo m Dados dois inteiros a e b e um inteiro positivo m dizemos que a e congruente a b modulo m se e somente se ma b Notacao Escrevese a b mod m para dizer que a e congruente a b modulo m Escrevese a b mod m para dizer que a nao e congruente a b modulo m Exemplo 370 114 mod 256 370 142 mod 256 142 114 mod 256 400 114 mod 256 370 400 mod 256 30 Congruˆencia modular Definicao Congruˆencia modulo m Dados dois inteiros a e b e um inteiro positivo m dizemos que a e congruente a b modulo m se e somente se ma b Notacao Escrevese a b mod m para dizer que a e congruente a b modulo m Escrevese a b mod m para dizer que a nao e congruente a b modulo m Observacao 2 Dizemos que uma expressao do tipo a b mod m e uma congruˆencia e que m e o seu modulo 31 Congruˆencia modular Definicao Congruˆencia modulo m Reescrita Dados dois inteiros a e b e um inteiro positivo m dizemos que a b mod m se e somente se ma b Notacao Escrevese a b mod m para dizer que a e congruente a b modulo m Escrevese a b mod m para dizer que a nao e congruente a b modulo m Observacao 2 Dizemos que uma expressao do tipo a b mod m e uma congruˆencia e que m e o seu modulo 32 Congruˆencia modular Observacao 1 Embora a relacao a b mod m e a funcao a mod m b sejam ambos escritos com a palavra mod estas expressoes tˆem significados muito diferentes Contudo a relacao a b mod m e a funcao a mod m b estao fortemente relacionadas Teorema 710 Sejam a e b inteiros e seja m um inteiro positivo Entao a b mod m se e somente se a mod m b mod m Demonstracao Deixada como exercıcio Teorema 711 Se a e um inteiro e m e um inteiro positivo entao a a mod m mod m Demonstracao Deixada como exercıcio 33 Congruˆencia modular Observacao 1 Embora a relacao a b mod m e a funcao a mod m b sejam ambos escritos com a palavra mod estas expressoes tˆem significados muito diferentes Contudo a relacao a b mod m e a funcao a mod m b estao fortemente relacionadas Teorema 710 Sejam a e b inteiros e seja m um inteiro positivo Entao a b mod m se e somente se a mod m b mod m Demonstracao Deixada como exercıcio Teorema 711 Se a e um inteiro e m e um inteiro positivo entao a a mod m mod m Demonstracao Deixada como exercıcio 33 Congruˆencia modular Observacao 1 Embora a relacao a b mod m e a funcao a mod m b sejam ambos escritos com a palavra mod estas expressoes tˆem significados muito diferentes Contudo a relacao a b mod m e a funcao a mod m b estao fortemente relacionadas Teorema 710 Sejam a e b inteiros e seja m um inteiro positivo Entao a b mod m se e somente se a mod m b mod m Demonstracao Deixada como exercıcio Teorema 711 Se a e um inteiro e m e um inteiro positivo entao a a mod m mod m Demonstracao Deixada como exercıcio 33 Congruˆencia modular Observacao 1 Embora a relacao a b mod m e a funcao a mod m b sejam ambos escritos com a palavra mod estas expressoes tˆem significados muito diferentes Contudo a relacao a b mod m e a funcao a mod m b estao fortemente relacionadas Teorema 710 Sejam a e b inteiros e seja m um inteiro positivo Entao a b mod m se e somente se a mod m b mod m Demonstracao Deixada como exercıcio Teorema 711 Se a e um inteiro e m e um inteiro positivo entao a a mod m mod m Demonstracao Deixada como exercıcio 33 Propriedades de Congruˆencias Modulares 34 Propriedades de Congruˆencias Modulares A notacao sugere que queremos considerar a relacao de congruˆencia modular como um analogo a relacao de igualdade De fato muitas das propriedades da igualdade sao validas para congruˆencias pelo menos quando mantemos o modulo fixo Assim como a igualdade a congruˆencia modular tambem satisfaz as seguintes propriedades Reflexividade a a mod m Simetria a b mod m b a mod m Transitividade a b mod m e b c mod m a c mod m 35 Propriedades de Congruˆencias Modulares A notacao sugere que queremos considerar a relacao de congruˆencia modular como um analogo a relacao de igualdade De fato muitas das propriedades da igualdade sao validas para congruˆencias pelo menos quando mantemos o modulo fixo Assim como a igualdade a congruˆencia modular tambem satisfaz as seguintes propriedades Reflexividade a a mod m Simetria a b mod m b a mod m Transitividade a b mod m e b c mod m a c mod m 35 Propriedades de Congruˆencias Modulares A notacao sugere que queremos considerar a relacao de congruˆencia modular como um analogo a relacao de igualdade De fato muitas das propriedades da igualdade sao validas para congruˆencias pelo menos quando mantemos o modulo fixo Assim como a igualdade a congruˆencia modular tambem satisfaz as seguintes propriedades Reflexividade a a mod m Simetria a b mod m b a mod m Transitividade a b mod m e b c mod m a c mod m 35 Propriedades de Congruˆencias Modulares A notacao sugere que queremos considerar a relacao de congruˆencia modular como um analogo a relacao de igualdade De fato muitas das propriedades da igualdade sao validas para congruˆencias pelo menos quando mantemos o modulo fixo Assim como a igualdade a congruˆencia modular tambem satisfaz as seguintes propriedades Reflexividade a a mod m Simetria a b mod m b a mod m Transitividade a b mod m e b c mod m a c mod m 35 Propriedades de Congruˆencias Modulares A notacao sugere que queremos considerar a relacao de congruˆencia modular como um analogo a relacao de igualdade De fato muitas das propriedades da igualdade sao validas para congruˆencias pelo menos quando mantemos o modulo fixo Assim como a igualdade a congruˆencia modular tambem satisfaz as seguintes propriedades Reflexividade a a mod m Simetria a b mod m b a mod m Transitividade a b mod m e b c mod m a c mod m 35 Propriedades de Congruˆencias Modulares Proposicao 712 Reflexividade Se a e m sao inteiros com m 1 entao a a mod m Demonstracao Seja m um inteiro positivo qualquer e a um inteiro qualquer Note que a a 0 e multiplo de m pois existe um inteiro k tal que 0 km neste caso temos k 0 Pela definicao de divisibilidade ma a Logo a a mod m pela definicao de congruˆencia modular 36 Propriedades de Congruˆencias Modulares Proposicao 712 Reflexividade Se a e m sao inteiros com m 1 entao a a mod m Demonstracao Seja m um inteiro positivo qualquer e a um inteiro qualquer Note que a a 0 e multiplo de m pois existe um inteiro k tal que 0 km neste caso temos k 0 Pela definicao de divisibilidade ma a Logo a a mod m pela definicao de congruˆencia modular 36 Propriedades de Congruˆencias Modulares Proposicao 712 Reflexividade Se a e m sao inteiros com m 1 entao a a mod m Demonstracao Seja m um inteiro positivo qualquer e a um inteiro qualquer Note que a a 0 e multiplo de m pois existe um inteiro k tal que 0 km neste caso temos k 0 Pela definicao de divisibilidade ma a Logo a a mod m pela definicao de congruˆencia modular 36 Propriedades de Congruˆencias Modulares Proposicao 712 Reflexividade Se a e m sao inteiros com m 1 entao a a mod m Demonstracao Seja m um inteiro positivo qualquer e a um inteiro qualquer Note que a a 0 e multiplo de m pois existe um inteiro k tal que 0 km neste caso temos k 0 Pela definicao de divisibilidade ma a Logo a a mod m pela definicao de congruˆencia modular 36 Propriedades de Congruˆencias Modulares Proposicao 712 Reflexividade Se a e m sao inteiros com m 1 entao a a mod m Demonstracao Seja m um inteiro positivo qualquer e a um inteiro qualquer Note que a a 0 e multiplo de m pois existe um inteiro k tal que 0 km neste caso temos k 0 Pela definicao de divisibilidade ma a Logo a a mod m pela definicao de congruˆencia modular 36 Propriedades de Congruˆencias Modulares Proposicao 713 Simetria Sejam a b e m inteiros com m 1 Se a b mod m entao b a mod m Demonstracao Seja m um inteiro positivo qualquer e a b inteiros quaisquer Suponha a b mod m Por definicao de congruˆencia modular ma b ou seja existe inteiro k tal que a b km Logo a b km b a km b a km b a km b a km Segue da ultima igualdade que mb a Logo pela definicao de congruˆencia modular b a mod m 37 Propriedades de Congruˆencias Modulares Proposicao 713 Simetria Sejam a b e m inteiros com m 1 Se a b mod m entao b a mod m Demonstracao Seja m um inteiro positivo qualquer e a b inteiros quaisquer Suponha a b mod m Por definicao de congruˆencia modular ma b ou seja existe inteiro k tal que a b km Logo a b km b a km b a km b a km b a km Segue da ultima igualdade que mb a Logo pela definicao de congruˆencia modular b a mod m 37 Propriedades de Congruˆencias Modulares Proposicao 713 Simetria Sejam a b e m inteiros com m 1 Se a b mod m entao b a mod m Demonstracao Seja m um inteiro positivo qualquer e a b inteiros quaisquer Suponha a b mod m Por definicao de congruˆencia modular ma b ou seja existe inteiro k tal que a b km Logo a b km b a km b a km b a km b a km Segue da ultima igualdade que mb a Logo pela definicao de congruˆencia modular b a mod m 37 Propriedades de Congruˆencias Modulares Proposicao 713 Simetria Sejam a b e m inteiros com m 1 Se a b mod m entao b a mod m Demonstracao Seja m um inteiro positivo qualquer e a b inteiros quaisquer Suponha a b mod m Por definicao de congruˆencia modular ma b ou seja existe inteiro k tal que a b km Logo a b km b a km b a km b a km b a km Segue da ultima igualdade que mb a Logo pela definicao de congruˆencia modular b a mod m 37 Propriedades de Congruˆencias Modulares Proposicao 713 Simetria Sejam a b e m inteiros com m 1 Se a b mod m entao b a mod m Demonstracao Seja m um inteiro positivo qualquer e a b inteiros quaisquer Suponha a b mod m Por definicao de congruˆencia modular ma b ou seja existe inteiro k tal que a b km Logo a b km b a km b a km b a km b a km Segue da ultima igualdade que mb a Logo pela definicao de congruˆencia modular b a mod m 37 Propriedades de Congruˆencias Modulares Proposicao 713 Simetria Sejam a b e m inteiros com m 1 Se a b mod m entao b a mod m Demonstracao Seja m um inteiro positivo qualquer e a b inteiros quaisquer Suponha a b mod m Por definicao de congruˆencia modular ma b ou seja existe inteiro k tal que a b km Logo a b km b a km b a km b a km b a km Segue da ultima igualdade que mb a Logo pela definicao de congruˆencia modular b a mod m 37 Propriedades de Congruˆencias Modulares Proposicao 714 Transitividade Sejam a b c e m inteiros com m 1 Se a b mod m e b c mod m entao a c mod m Demonstracao Deixada como exercıcio 38 Propriedades de Congruˆencias Modulares Outros teoremas deixados como exercıcio Teorema 715 Sejam a e m inteiros com m 1 Entao a 0 mod m se e somente se ma Teorema 716 Sejam a b c e m inteiros com m 1 Se a c mod m e b c mod m entao a b mod m Teorema 717 Sejam a b e m inteiros com m 1 Os inteiros a e b sao congruentes modulo m se e somente se existe um inteiro k tal que a b km 39 Propriedades de Congruˆencias Modulares Outros teoremas deixados como exercıcio Teorema 715 Sejam a e m inteiros com m 1 Entao a 0 mod m se e somente se ma Teorema 716 Sejam a b c e m inteiros com m 1 Se a c mod m e b c mod m entao a b mod m Teorema 717 Sejam a b e m inteiros com m 1 Os inteiros a e b sao congruentes modulo m se e somente se existe um inteiro k tal que a b km 39 Propriedades de Congruˆencias Modulares Outros teoremas deixados como exercıcio Teorema 715 Sejam a e m inteiros com m 1 Entao a 0 mod m se e somente se ma Teorema 716 Sejam a b c e m inteiros com m 1 Se a c mod m e b c mod m entao a b mod m Teorema 717 Sejam a b e m inteiros com m 1 Os inteiros a e b sao congruentes modulo m se e somente se existe um inteiro k tal que a b km 39 Propriedades de Congruˆencias Modulares Congruˆencias tambem se comportam como igualdades no seguinte aspecto Se vocˆe tiver duas congruˆencias com o mesmo modulo a b mod m e c d mod m entao podemos adicionalas subtraılas ou multiplicalas a c b d mod m a c b d mod m ac bd mod m Precisamos provar essas afirmacoes 40 Propriedades de Congruˆencias Modulares Teorema 718 Sejam a b c d e m inteiros com m 1 Se a b mod m e c d mod m entao 1 a c b d mod m e 2 a c b d mod m e 3 ac bd mod m Demonstracao Vamos usar prova direta Suponha a b mod m e c d mod m Pelo Teorema 717 existem inteiros s e t tais que b a sm e d c tm Deste modo temos que b d a sm c tm a c ms t b d a sm c tm a c ms t bd a smc tm ac mat cs stm 41 Propriedades de Congruˆencias Modulares Teorema 718 Sejam a b c d e m inteiros com m 1 Se a b mod m e c d mod m entao 1 a c b d mod m e 2 a c b d mod m e 3 ac bd mod m Demonstracao Vamos usar prova direta Suponha a b mod m e c d mod m Pelo Teorema 717 existem inteiros s e t tais que b a sm e d c tm Deste modo temos que b d a sm c tm a c ms t b d a sm c tm a c ms t bd a smc tm ac mat cs stm 41 Propriedades de Congruˆencias Modulares Teorema 718 Sejam a b c d e m inteiros com m 1 Se a b mod m e c d mod m entao 1 a c b d mod m e 2 a c b d mod m e 3 ac bd mod m Demonstracao Vamos usar prova direta Suponha a b mod m e c d mod m Pelo Teorema 717 existem inteiros s e t tais que b a sm e d c tm Deste modo temos que b d a sm c tm a c ms t b d a sm c tm a c ms t bd a smc tm ac mat cs stm 41 Propriedades de Congruˆencias Modulares Teorema 718 Sejam a b c d e m inteiros com m 1 Se a b mod m e c d mod m entao 1 a c b d mod m e 2 a c b d mod m e 3 ac bd mod m Demonstracao Vamos usar prova direta Suponha a b mod m e c d mod m Pelo Teorema 717 existem inteiros s e t tais que b a sm e d c tm Deste modo temos que b d a sm c tm a c ms t b d a sm c tm a c ms t bd a smc tm ac mat cs stm 41 Propriedades de Congruˆencias Modulares Teorema 718 Sejam a b c d e m inteiros com m 1 Se a b mod m e c d mod m entao 1 a c b d mod m e 2 a c b d mod m e 3 ac bd mod m Demonstracao Vamos usar prova direta Suponha a b mod m e c d mod m Pelo Teorema 717 existem inteiros s e t tais que b a sm e d c tm Deste modo temos que b d a sm c tm a c ms t b d a sm c tm a c ms t bd a smc tm ac mat cs stm 41 Propriedades de Congruˆencias Modulares Teorema 718 Sejam a b c d e m inteiros com m 1 Se a b mod m e c d mod m entao 1 a c b d mod m e 2 a c b d mod m e 3 ac bd mod m Demonstracao Vamos usar prova direta Suponha a b mod m e c d mod m Pelo Teorema 717 existem inteiros s e t tais que b a sm e d c tm Deste modo temos que b d a c ms t b d a c ms t bd ac mat cs stm Entao pelo Teorema 717 temos que a c b d mod m e a c b d mod m e ac bd mod m 42 Propriedades de Congruˆencias Modulares Teorema 718 Sejam a b c d e m inteiros com m 1 Se a b mod m e c d mod m entao 1 a c b d mod m e 2 a c b d mod m e 3 ac bd mod m Demonstracao Vamos usar prova direta Suponha a b mod m e c d mod m Pelo Teorema 717 existem inteiros s e t tais que b a sm e d c tm Deste modo temos que b d a c ms t b d a c ms t bd ac mat cs stm Entao pelo Teorema 717 temos que a c b d mod m e a c b d mod m e ac bd mod m 42 Propriedades de Congruˆencias Modulares Exercıcio Usando o Teorema 718 o Teorema 710 e o Teorema 711 prove Corolario 719 Seja m inteiro positivo e a b inteiros Entao a b mod m a mod m b mod m mod m e a b mod m a mod m b mod m mod m Demonstracao Deixada como exercıcio 43 Aritmética módulo m Aritmetica modulo m Suponha que agora sao 2 horas da tarde ou da madrugada tanto faz E considere as horas contadas no formato de 12h Ou seja as horas possıveis estao no conjunto 0 1 2 11 Em nosso relogio a hora 0 corresponde aos ponteiros no numero 12 Que horas serao daqui a 5 horas Resposta 2 5 mod 12 7 horas Que horas serao daqui a 24 horas Resposta 2 24 mod 12 26 mod 12 2 horas Que horas o relogio marcava ha 4 horas atras Resposta 2 4 mod 12 2 mod 12 10 horas 45 Aritmetica modulo m Suponha que agora sao 2 horas da tarde ou da madrugada tanto faz E considere as horas contadas no formato de 12h Ou seja as horas possıveis estao no conjunto 0 1 2 11 Em nosso relogio a hora 0 corresponde aos ponteiros no numero 12 Que horas serao daqui a 5 horas Resposta 2 5 mod 12 7 horas Que horas serao daqui a 24 horas Resposta 2 24 mod 12 26 mod 12 2 horas Que horas o relogio marcava ha 4 horas atras Resposta 2 4 mod 12 2 mod 12 10 horas 45 Aritmetica modulo m Suponha que agora sao 2 horas da tarde ou da madrugada tanto faz E considere as horas contadas no formato de 12h Ou seja as horas possıveis estao no conjunto 0 1 2 11 Em nosso relogio a hora 0 corresponde aos ponteiros no numero 12 Que horas serao daqui a 5 horas Resposta 2 5 mod 12 7 horas Que horas serao daqui a 24 horas Resposta 2 24 mod 12 26 mod 12 2 horas Que horas o relogio marcava ha 4 horas atras Resposta 2 4 mod 12 2 mod 12 10 horas 45 Aritmetica modulo m Suponha que agora sao 2 horas da tarde ou da madrugada tanto faz E considere as horas contadas no formato de 12h Ou seja as horas possıveis estao no conjunto 0 1 2 11 Em nosso relogio a hora 0 corresponde aos ponteiros no numero 12 Que horas serao daqui a 5 horas Resposta 2 5 mod 12 7 horas Que horas serao daqui a 24 horas Resposta 2 24 mod 12 26 mod 12 2 horas Que horas o relogio marcava ha 4 horas atras Resposta 2 4 mod 12 2 mod 12 10 horas 45 Aritmetica modulo m Suponha que agora sao 2 horas da tarde ou da madrugada tanto faz E considere as horas contadas no formato de 12h Ou seja as horas possıveis estao no conjunto 0 1 2 11 Em nosso relogio a hora 0 corresponde aos ponteiros no numero 12 Que horas serao daqui a 5 horas Resposta 2 5 mod 12 7 horas Que horas serao daqui a 24 horas Resposta 2 24 mod 12 26 mod 12 2 horas Que horas o relogio marcava ha 4 horas atras Resposta 2 4 mod 12 2 mod 12 10 horas 45 Aritmetica modulo m Suponha que agora sao 2 horas da tarde ou da madrugada tanto faz E considere as horas contadas no formato de 12h Ou seja as horas possıveis estao no conjunto 0 1 2 11 Em nosso relogio a hora 0 corresponde aos ponteiros no numero 12 Que horas serao daqui a 5 horas Resposta 2 5 mod 12 7 horas Que horas serao daqui a 24 horas Resposta 2 24 mod 12 26 mod 12 2 horas Que horas o relogio marcava ha 4 horas atras Resposta 2 4 mod 12 2 mod 12 10 horas 45 Aritmetica modulo m Suponha que agora sao 2 horas da tarde ou da madrugada tanto faz E considere as horas contadas no formato de 12h Ou seja as horas possıveis estao no conjunto 0 1 2 11 Em nosso relogio a hora 0 corresponde aos ponteiros no numero 12 Que horas serao daqui a 5 horas Resposta 2 5 mod 12 7 horas Que horas serao daqui a 24 horas Resposta 2 24 mod 12 26 mod 12 2 horas Que horas o relogio marcava ha 4 horas atras Resposta 2 4 mod 12 2 mod 12 10 horas 45 Aritmética módulo m O que é Aritmética É o ramo da matemática que estuda a manipulação de números e as propriedades sobre estes Aritmética módulo m O que é Aritmética É o ramo da matemática que estuda a manipulação de números e as propriedades sobre estes O que torna uma Aritmética Modular É uma aritmética restrita aos restos de divisão pelo módulo m Após cada operação aplicase a função mod m para corrigir resultados Aritmética módulo m O que é Aritmética É o ramo da matemática que estuda a manipulação de números e as propriedades sobre estes O que torna uma Aritmética Modular É uma aritmética restrita aos restos de divisão pelo módulo m Após cada operação aplicase a função mod m para corrigir resultados Exemplo Na aritmética de módulo 12 ao somar 5 e 130 faremos 5 130 mod 12 135 mod 12 3 soma modular resultado 46 Aritmética módulo m O que é Aritmética É o ramo da matemática que estuda a manipulação de números e as propriedades sobre estes O que torna uma Aritmética Modular É uma aritmética restrita aos restos de divisão pelo módulo m Após cada operação aplicase a função mod m para corrigir resultados Exemplo Na aritmética de módulo 12 ao multiplicar 5 e 130 faremos 5 130 mod 12 650 mod 12 2 multiplicação modular resultado 47 Domınio Zm Definicao Domınio Zm Dado um inteiro m 0 o domınio da aritmetica de modulo m e o conjunto Zm 0 1 m 1 Exemplos A aritmetica de modulo 1 tem como domınio Z1 0 de modulo 2 tem como domınio Z2 0 1 de modulo 5 tem como domınio Z5 0 1 4 de modulo 12 tem como domınio Z12 0 1 11 de modulo 60 tem como domınio Z60 0 1 59 de modulo 256 tem como domınio Z256 0 1 255 48 Domınio Zm Definicao Domınio Zm Dado um inteiro m 0 o domınio da aritmetica de modulo m e o conjunto Zm 0 1 m 1 Exemplos A aritmetica de modulo 1 tem como domınio Z1 0 de modulo 2 tem como domınio Z2 0 1 de modulo 5 tem como domınio Z5 0 1 4 de modulo 12 tem como domınio Z12 0 1 11 de modulo 60 tem como domınio Z60 0 1 59 de modulo 256 tem como domınio Z256 0 1 255 48 Domınio Zm Definicao Domınio Zm Dado um inteiro m 0 o domınio da aritmetica de modulo m e o conjunto Zm 0 1 m 1 Exemplos A aritmetica de modulo 1 tem como domınio Z1 0 de modulo 2 tem como domınio Z2 0 1 de modulo 5 tem como domınio Z5 0 1 4 de modulo 12 tem como domınio Z12 0 1 11 de modulo 60 tem como domınio Z60 0 1 59 de modulo 256 tem como domınio Z256 0 1 255 48 Domınio Zm Definicao Domınio Zm Dado um inteiro m 0 o domınio da aritmetica de modulo m e o conjunto Zm 0 1 m 1 Exemplos A aritmetica de modulo 1 tem como domınio Z1 0 de modulo 2 tem como domınio Z2 0 1 de modulo 5 tem como domınio Z5 0 1 4 de modulo 12 tem como domınio Z12 0 1 11 de modulo 60 tem como domınio Z60 0 1 59 de modulo 256 tem como domınio Z256 0 1 255 48 Domınio Zm Definicao Domınio Zm Dado um inteiro m 0 o domınio da aritmetica de modulo m e o conjunto Zm 0 1 m 1 Exemplos A aritmetica de modulo 1 tem como domınio Z1 0 de modulo 2 tem como domınio Z2 0 1 de modulo 5 tem como domınio Z5 0 1 4 de modulo 12 tem como domınio Z12 0 1 11 de modulo 60 tem como domınio Z60 0 1 59 de modulo 256 tem como domınio Z256 0 1 255 48 Operacoes em Zm Definicao Operacoes em Zm Dado um inteiro m 0 e a b Zm a m b a b mod m soma modulo m a m b a b mod m multiplicacao modulo m Exemplo Soma 7 11 9 7 9 mod 11 16 mod 11 5 Operacoes aritmeticas de modulo 11 fun cionam como em um relogio hipotetico de 11 horas 0 1 2 3 4 5 6 7 8 9 10 49 Operacoes em Zm Definicao Operacoes em Zm Dado um inteiro m 0 e a b Zm a m b a b mod m soma modulo m a m b a b mod m multiplicacao modulo m Exemplo Soma 7 11 9 7 9 mod 11 16 mod 11 5 Operacoes aritmeticas de modulo 11 fun cionam como em um relogio hipotetico de 11 horas 0 1 2 3 4 5 6 7 8 9 10 49 Operacoes em Zm Definicao Operacoes em Zm Dado um inteiro m 0 e a b Zm a m b a b mod m soma modulo m a m b a b mod m multiplicacao modulo m Exemplo Soma 7 11 9 7 9 mod 11 16 mod 11 5 Operacoes aritmeticas de modulo 11 fun cionam como em um relogio hipotetico de 11 horas 0 1 2 3 4 5 6 7 8 9 10 49 Operacoes em Zm Similarmente teremos 453 43 mod 5 7 mod 5 2 0 1 2 3 4 5 583 53 mod 8 8 mod 8 0 0 1 2 3 4 5 6 7 50 Operacoes em Zm Similarmente teremos 453 43 mod 5 7 mod 5 2 0 1 2 3 4 5 583 53 mod 8 8 mod 8 0 0 1 2 3 4 5 6 7 50 Definicao Aritmetica de modulo m Definicao Domınio Zm Dado um inteiro m 0 o domınio da aritmetica de modulo m e o conjunto Zm 0 1 m 1 Definicao Operacoes em Zm Dado um inteiro m 0 e a b Zm a m b a b mod m soma modulo m a m b a b mod m multiplicacao modulo m Definicao Aritmetica de modulo m Dado um inteiro m 0 a aritmetica de modulo m e a estrutura Zm m m 51 Definicao Aritmetica de modulo m Definicao Domınio Zm Dado um inteiro m 0 o domınio da aritmetica de modulo m e o conjunto Zm 0 1 m 1 Definicao Operacoes em Zm Dado um inteiro m 0 e a b Zm a m b a b mod m soma modulo m a m b a b mod m multiplicacao modulo m Definicao Aritmetica de modulo m Dado um inteiro m 0 a aritmetica de modulo m e a estrutura Zm m m 51 Propriedades das Operacoes no Modulo m 52 Propriedades das operacoes no modulo m Dado um inteiro m 0 as operacoes m e m satisfazem as propriedades abaixo para todos a b c Zm Fechamento 1 a m b Zm 2 a m b Zm Associatividade 1 a m b m c a m b m c 2 a m b m c a m b m c Comutatividade 1 a m b b m a 2 a m b b m a Distributividade 1 a m b m c a m bm a m c Elemento Neutro 1 a m 0 a 2 a m 1 a Inverso Aditivo 1 se a 0 a m m a 0 2 0 m 0 0 Demonstrar estas propriedades e um excelente exercıcio 53 Propriedades das operacoes no modulo m Dado um inteiro m 0 as operacoes m e m satisfazem as propriedades abaixo para todos a b c Zm Fechamento 1 a m b Zm 2 a m b Zm Associatividade 1 a m b m c a m b m c 2 a m b m c a m b m c Comutatividade 1 a m b b m a 2 a m b b m a Distributividade 1 a m b m c a m bm a m c Elemento Neutro 1 a m 0 a 2 a m 1 a Inverso Aditivo 1 se a 0 a m m a 0 2 0 m 0 0 Demonstrar estas propriedades e um excelente exercıcio 53 Propriedades das operacoes no modulo m Dado um inteiro m 0 as operacoes m e m satisfazem as propriedades abaixo para todos a b c Zm Fechamento 1 a m b Zm 2 a m b Zm Associatividade 1 a m b m c a m b m c 2 a m b m c a m b m c Comutatividade 1 a m b b m a 2 a m b b m a Distributividade 1 a m b m c a m bm a m c Elemento Neutro 1 a m 0 a 2 a m 1 a Inverso Aditivo 1 se a 0 a m m a 0 2 0 m 0 0 Demonstrar estas propriedades e um excelente exercıcio 53 Propriedades das operacoes no modulo m Dado um inteiro m 0 as operacoes m e m satisfazem as propriedades abaixo para todos a b c Zm Fechamento 1 a m b Zm 2 a m b Zm Associatividade 1 a m b m c a m b m c 2 a m b m c a m b m c Comutatividade 1 a m b b m a 2 a m b b m a Distributividade 1 a m b m c a m bm a m c Elemento Neutro 1 a m 0 a 2 a m 1 a Inverso Aditivo 1 se a 0 a m m a 0 2 0 m 0 0 Demonstrar estas propriedades e um excelente exercıcio 53 Propriedades das operacoes no modulo m Dado um inteiro m 0 as operacoes m e m satisfazem as propriedades abaixo para todos a b c Zm Fechamento 1 a m b Zm 2 a m b Zm Associatividade 1 a m b m c a m b m c 2 a m b m c a m b m c Comutatividade 1 a m b b m a 2 a m b b m a Distributividade 1 a m b m c a m bm a m c Elemento Neutro 1 a m 0 a 2 a m 1 a Inverso Aditivo 1 se a 0 a m m a 0 2 0 m 0 0 Demonstrar estas propriedades e um excelente exercıcio 53 Propriedades das operacoes no modulo m Dado um inteiro m 0 as operacoes m e m satisfazem as propriedades abaixo para todos a b c Zm Fechamento 1 a m b Zm 2 a m b Zm Associatividade 1 a m b m c a m b m c 2 a m b m c a m b m c Comutatividade 1 a m b b m a 2 a m b b m a Distributividade 1 a m b m c a m bm a m c Elemento Neutro 1 a m 0 a 2 a m 1 a Inverso Aditivo 1 se a 0 a m m a 0 2 0 m 0 0 Demonstrar estas propriedades e um excelente exercıcio 53 Propriedades das operacoes no modulo m Dado um inteiro m 0 as operacoes m e m satisfazem as propriedades abaixo para todos a b c Zm Fechamento 1 a m b Zm 2 a m b Zm Associatividade 1 a m b m c a m b m c 2 a m b m c a m b m c Comutatividade 1 a m b b m a 2 a m b b m a Distributividade 1 a m b m c a m bm a m c Elemento Neutro 1 a m 0 a 2 a m 1 a Inverso Aditivo 1 se a 0 a m m a 0 2 0 m 0 0 Demonstrar estas propriedades e um excelente exercıcio 53 Propriedades das operacoes no modulo m A tıtulo de exemplo demonstraremos a comutatividade da soma Teorema 720 Comutatividade de m Dado um inteiro m 0 se a b Zm entao a m b b m a Demonstracao Sejam m um inteiro positivo qualquer e a b inteiros quaisquer Por prova direta suponha que a b Zm Pela definicao da soma modular temos a m b a b mod m b a mod m comutatividade em Z b m a definicao de m Portanto a m b b m a Como exercıcio demonstre as demais propriedades 54 Propriedades das operacoes no modulo m A tıtulo de exemplo demonstraremos a comutatividade da soma Teorema 720 Comutatividade de m Dado um inteiro m 0 se a b Zm entao a m b b m a Demonstracao Sejam m um inteiro positivo qualquer e a b inteiros quaisquer Por prova direta suponha que a b Zm Pela definicao da soma modular temos a m b a b mod m b a mod m comutatividade em Z b m a definicao de m Portanto a m b b m a Como exercıcio demonstre as demais propriedades 54 Propriedades das operacoes no modulo m A tıtulo de exemplo demonstraremos a comutatividade da soma Teorema 720 Comutatividade de m Dado um inteiro m 0 se a b Zm entao a m b b m a Demonstracao Sejam m um inteiro positivo qualquer e a b inteiros quaisquer Por prova direta suponha que a b Zm Pela definicao da soma modular temos a m b a b mod m b a mod m comutatividade em Z b m a definicao de m Portanto a m b b m a Como exercıcio demonstre as demais propriedades 54 Propriedades das operacoes no modulo m A tıtulo de exemplo demonstraremos a comutatividade da soma Teorema 720 Comutatividade de m Dado um inteiro m 0 se a b Zm entao a m b b m a Demonstracao Sejam m um inteiro positivo qualquer e a b inteiros quaisquer Por prova direta suponha que a b Zm Pela definicao da soma modular temos a m b a b mod m b a mod m comutatividade em Z b m a definicao de m Portanto a m b b m a Como exercıcio demonstre as demais propriedades 54 Propriedades das operacoes no modulo m A tıtulo de exemplo demonstraremos a comutatividade da soma Teorema 720 Comutatividade de m Dado um inteiro m 0 se a b Zm entao a m b b m a Demonstracao Sejam m um inteiro positivo qualquer e a b inteiros quaisquer Por prova direta suponha que a b Zm Pela definicao da soma modular temos a m b a b mod m b a mod m comutatividade em Z b m a definicao de m Portanto a m b b m a Como exercıcio demonstre as demais propriedades 54 Propriedades das operacoes no modulo m A tıtulo de exemplo demonstraremos a comutatividade da soma Teorema 720 Comutatividade de m Dado um inteiro m 0 se a b Zm entao a m b b m a Demonstracao Sejam m um inteiro positivo qualquer e a b inteiros quaisquer Por prova direta suponha que a b Zm Pela definicao da soma modular temos a m b a b mod m b a mod m comutatividade em Z b m a definicao de m Portanto a m b b m a Como exercıcio demonstre as demais propriedades 54 FIM