{"id":1863,"date":"2022-10-02T14:27:19","date_gmt":"2022-10-02T17:27:19","guid":{"rendered":"http:\/\/localhost\/?page_id=1863"},"modified":"2022-10-04T11:09:51","modified_gmt":"2022-10-04T14:09:51","slug":"congruencias","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/fundamentos-de-algebra\/congruencias\/","title":{"rendered":"Congru\u00eancias"},"content":{"rendered":"
\n
\nSejam $a,b\\in\\Z$ e seja $n\\in\\N$. Dizemos que $a$ \u00e9 congruente com $b$ m\u00f3dulo $n$ se $n\\mid a-b$. Neste caso, escrevemos que $a\\equiv b\\pmod n$ ou $a\\equiv b\\,(n)$.<\/div>\n
\nPor exemplo, $2\\equiv 7\\pmod 5$, $1\\equiv -5\\pmod6$, mas $-2\\not\\equiv 3\\pmod 4$.<\/div>\n
\nSejam $a,b,n$ como na defini\u00e7\u00e3o anterior e escreva $a=q_an+r_a$ e $b=q_bn+r_b$ com $r_a,r_b\\in\\{0,\\ldots,n-1\\}$. Temos que $a\\equiv b\\pmod n$ se e somente se $r_a=r_b$.<\/div>\n
\nAssuma que $r_a=r_b$. Ent\u00e3o
\n$$
\na-b=q_an+r_a-q_bn-r_b=n(q_a-q_b)
\n$$
\ne neste caso $n\\mid a-b$. Assuma agora que $n\\mid a-b$ e assuma ainda sem perder generalidade que $r_a\\geq r_b$. Ora
\n$$
\na-b=(q_a-q_b)n+(r_a-r_b).
\n$$
\nComo $n\\mid a-b$, temos que $n\\mid r_a-r_b$. Por outro lado, pelas suposi\u00e7\u00f5es,
\n\\[
\n0\\leq r_a-r_b\\leq n-1.
\n\\]
\nO \u00fanico n\u00famero entre $0$ e $n-1$ que seja divs\u00edvel por $n$ \u00e9 o zero e assim $r_a-r_b=0$; ou seja $r_a=r_b$.<\/div>\n

Pelo resultado anterior, temos que $a\\equiv b\\pmod n$ se e somente se os restos de $a$ e $b$ quando divididos por $n$ s\u00e3o iguais.<\/p>\n

\nSeja $a=31$, $b=-83$ e $n=6$. Temos que
\n\\[
\n31=5\\cdot 6+1\\quad\\mbox{e}\\quad -83=-14\\cdot 6+1.
\n\\]
\nLogo $31\\equiv -83\\pmod 6$. De fato, pode-se verificar o mesmo fato diretamente da defini\u00e7\u00e3o, pois
\n\\[
\n31-(-83)=114
\n\\]
\n\u00e9 divis\u00edvel por $6$.<\/div>\n
(As propriedades b\u00e1sicas)
\nAs seguintes s\u00e3o verdadeiras para todo $a,b,c\\in\\Z$ e $n\\in\\N$.<\/p>\n
    \n
  1. $a\\equiv a\\pmod n$ (reflexividade).<\/li>\n
  2. Se $a\\equiv b\\pmod n$, ent\u00e3o $b\\equiv a\\pmod n$ (simetria).<\/li>\n
  3. Se $a\\equiv b\\pmod n$ e $b\\equiv c\\pmod n$, ent\u00e3o $a\\equiv c\\pmod n$ (transitividade).<\/li>\n<\/ol>\n

    Em outras palavras, a rela\u00e7\u00e3o de “ser congru\u00eante m\u00f3dulo $n$” \u00e9 uma rela\u00e7\u00e3o de equival\u00eancia no conjunto $\\Z$.<\/p>\n<\/div>\n

    \nAs propriedades 1. e 2. s\u00e3o t\u00e3o simples que vamos deixar a prova para o leitor. Considere afirma\u00e7\u00e3o 3. Assuma que
    \n$a\\equiv b\\pmod n$ e $b\\equiv c\\pmod n$. Por defini\u00e7\u00e3o, $n\\mid a-b$ e $n\\mid b-c$, e assim
    \n\\[
    \nn\\mid (a-b)+(b-c)=a-c.
    \n\\]
    \nUsando a defini\u00e7\u00e3o de novo, $a\\equiv c\\pmod n$.<\/div>\n

    Quando trabalhamos com n\u00fameros inteiros, usamos freq\u00eantamente que em express\u00f5es alg\u00e9bricas, quantidades podem ser substitu\u00eddas por outras quantidades iguais. Por exemplo, se $a_1=a_2$ e $b_1=b_2$, ent\u00e3o
    \n\\[
    \na_1+b_1=a_2+b_2\\quad\\mbox{e}\\quad a_1\\cdot b_1=a_2\\cdot b_2.
    \n\\]
    \nPelo lema seguinte, a mesma coisa est\u00e1 v\u00e1lida para congru\u00eancias.<\/p>\n

    (As regras da arim\u00e9tica)
    \nAssuma que $a_1,a_2,b_1,b_2\\in\\Z$ e $n\\in \\N$ tais que
    \n\\[
    \na_1\\equiv a_2\\pmod n\\quad\\mbox{e}\\quad b_1\\equiv b_2\\pmod n.
    \n\\]
    \nNeste caso,
    \n\\[
    \na_1+b_1\\equiv a_2+b_2\\!\\pmod n\\quad\\mbox{e}\\quad a_1\\cdot b_1\\equiv a_2\\cdot b_2\\!\\pmod n.
    \n\\]<\/div>\n
    \nVamos provar apenas a segunda afirma\u00e7\u00e3o; o leitor pode verificar facilmente a primeira. Como $a_1\\equiv a_2\\pmod n$ e $b_1\\equiv b_2\\pmod n$, segue que $n\\mid a_1-a_2$ e $n\\mid b_1-b_2$. Logo
    \n\\begin{align*}
    \nn&\\mid b_1(a_1-a_2)+a_2(b_1-b_2)=b_1a_1-b_1a_2+a_2b_1-a_2b_2\\\\&=a_1b_1-a_2b_2.
    \n\\end{align*}
    \nLogo $a_1b_1\\equiv a_2b_2\\pmod n$.<\/div>\n
    \nTemos que
    \n\\[
    \n6\\equiv -4\\quad\\mbox{e}\\quad 12\\equiv -3\\pmod 5.
    \n\\]
    \nEnt\u00e3o
    \n\\[
    \n6+12\\equiv -4-3\\quad\\mbox{e}\\quad 6\\cdot 12\\equiv(-4)\\cdot(-3)\\pmod 5.
    \n\\]
    \nDe fato a primeira congru\u00eancia diz que $18\\equiv -7\\pmod 5$ enquanto a segunda diz que $72\\equiv 12\\pmod 5$ e as duas s\u00e3o obviamente certas.<\/div>\n

    Apresentaremos, como uma aplica\u00e7\u00e3o destas regras da aritm\u00e9tica, uma forma alternativa dos crit\u00e9rios da divisibilidade.<\/p>\n

    (Os crit\u00e9rios da divisibilidade)
    \nSeja $a=[a_na_{n-1}\\cdots a_1a_0]_{10}$ um n\u00famero natural escrito na base decimal. As seguintes afirma\u00e7\u00f5es s\u00e3o verdadeiras.<\/p>\n
      \n
    1. $a\\equiv a_0\\pmod 2$;<\/li>\n
    2. $a\\equiv \\sum_{i\\geq 0} a_i\\pmod 3$;<\/li>\n
    3. $a\\equiv [a_1a_0]_{10}\\pmod 4$;<\/li>\n
    4. $a\\equiv a_0\\pmod 5$;<\/li>\n
    5. $a\\equiv 3([a_n\\cdots a_1]_{10}-2a_0)\\pmod 7$;<\/li>\n
    6. $a\\equiv [a_2a_1a_0]_{10}\\pmod 8$;<\/li>\n
    7. $a\\equiv \\sum_{i\\geq 0} a_i\\pmod 9$;<\/li>\n
    8. $a\\equiv \\sum_{i\\geq 0} (-1)^ia_i\\pmod{11}$<\/li>\n<\/ol>\n<\/div>\n
      \nVamos demonstrar as afirma\u00e7\u00f5es 2. e 5.; o resto ser\u00e1 exerc\u00edcio.<\/p>\n

      (2) Note primeiro que $10\\equiv 1\\pmod 3$ e assim o lema anterior implica que
      \n\\[
      \n10^k=10\\cdots 10\\equiv 1\\cdots 1=1\\pmod 3.
      \n\\]
      \nOu seja, $10^k\\equiv 1\\pmod 3$ para todo $k\\geq 0$. Ora,
      \n\\[
      \na=\\sum_{k=0}^n a_k10^k\\equiv \\sum_{k=0}^n a_k\\cdot 1=\\sum_{k=0}^n a_k\\pmod 3.
      \n\\]<\/p>\n

      (5) Calculemos que
      \n\\begin{align*}
      \n3([a_n\\cdots a_1]_{10}-2a_0)&=3\\frac{a-a_0}{10}-2a_0\\\\&=3\\frac{a-21a_0}{10}\\equiv 10\\frac{a-21\\cdot a_0}{10}\\\\&=a-21a_0\\equiv a\\pmod 7
      \n\\end{align*}<\/p>\n<\/div>\n

      Note que o teorema anterior pode ser visto como uma forma forte dos crit\u00e9rios da divisibilidade.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

      Sejam $a,b\\in\\Z$ e seja $n\\in\\N$. Dizemos que $a$ \u00e9 congruente com $b$ m\u00f3dulo $n$ se $n\\mid a-b$. Neste caso, escrevemos que $a\\equiv b\\pmod n$ ou $a\\equiv b\\,(n)$. Por exemplo, $2\\equiv 7\\pmod 5$, $1\\equiv -5\\pmod6$, mas $-2\\not\\equiv 3\\pmod 4$. Sejam $a,b,n$ como na defini\u00e7\u00e3o anterior e escreva $a=q_an+r_a$ e $b=q_bn+r_b$ com $r_a,r_b\\in\\{0,\\ldots,n-1\\}$. Temos que $a\\equiv b\\pmod … Continue reading Congru\u00eancias<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1193,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1863"}],"collection":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/comments?post=1863"}],"version-history":[{"count":4,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1863\/revisions"}],"predecessor-version":[{"id":1914,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1863\/revisions\/1914"}],"up":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1193"}],"wp:attachment":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/media?parent=1863"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}