UFRPE-DM Aula 03 - Congruência I

Seção 2.1 Aula 03 - Congruência I

Definição 2.1.1.

Dizemos que os inteiros \(a\) e \(b\) são congrentes módulo \(m\) se eles deixam o mesmo resto quando divididos por \(m\text{.}\) Denotaremos isso por \(a \equiv b \mod{m}\text{.}\)

Exemplo 2.1.2.

\begin{gather*} 7 \equiv 2 \mod 5,\\ 9 \equiv 3 \mod 6,\\ 37 \equiv 7 \mod 10,\\ 5\not\equiv 4 \mod{4}. \end{gather*}

Veja que \(a \equiv b \mod m\) se, e somente se, \(m | a - b\text{.}\)

Teorema 2.1.3.

Se \(a\equiv b \mod m\) e \(c\equiv d \mod m\text{,}\) então:

\(\displaystyle a+c \equiv b+d \mod m\)
\(\displaystyle a-c \equiv b-d \mod m\)
\(\displaystyle ka \equiv kb \mod m ~ \forall ~k\in \mathbb{Z}\)
\(\displaystyle ac\equiv bd \mod m\)
\(\displaystyle a^k \equiv b^k \mod m\)
\(ka\equiv kb \mod m\Leftrightarrow a\equiv b \mod \left(\dfrac{m}{mdc(k, m)}\right)\text{.}\)
\(a\equiv b \mod m_i,~\forall i=1, \ldots, r \Leftrightarrow a\equiv b \mod (mmc(m_1, \ldots, m_r))\text{.}\)

Exemplo 2.1.4.

Calcule o resto de \(4^{100}\) por \(3\text{.}\)

Solução

Observe que

\begin{equation*} 4\equiv 1 \mod 3. \end{equation*}

Pelo item v. do Teorema 2.1.3

\begin{equation*} 4^{100}\equiv 1^{100} \mod 3 \Rightarrow 4^{100} \equiv 1 \mod 3. \end{equation*}

Portanto, o resto é \(1\text{.}\)

Exemplo 2.1.5.

Calcule o resto de \(4^{100}\) por \(5\text{.}\)

Solução

Observe que

\begin{equation*} 4\equiv -1 \mod 5. \end{equation*}

Pelo item v. do Teorema 2.1.3

\begin{equation*} 4^{100}\equiv (-1)^{100} \mod 3 \Rightarrow 4^{100} \equiv 1 \mod 3. \end{equation*}

Portanto, o resto é \(1\text{.}\)

Exemplo 2.1.6.

Calcule o resto de \(4^{100}\) por \(7\text{.}\)

Solução

\begin{align*} 4 \equiv\amp~ 4 \mod 7\\ 4^2 \equiv\amp~ 16 \equiv 2 \mod 7\\ 4^3 \equiv\amp~ 2\cdot 4 \equiv 8 \mod 7\\ 4^3 \equiv\amp~ 1 \mod 7 \end{align*}

Queremos o resto da divisão de \(4^{100}\) por \(7\text{,}\) como \(100 = 3\cdot 33 +1\text{,}\) vamos usar a última conguência, e o item v. do Teorema 2.1.3 para \(k=33\text{,}\) logo:

\begin{equation*} (4^3)^{33} \equiv 1^{33} \mod 7. \end{equation*}

Agora, usando o item iii., com \(k=4\text{:}\)

\begin{align*} (4^3)^{33}\cdot 4 \equiv\amp~ 1\cdot 4 \mod 7\\ 4^{3\cdot 33+1} \equiv\amp~ 4 \mod 7\\ 4^{100} \equiv\amp~ 4 \mod 7 \end{align*}

Portanto, o resto é \(4\text{.}\)

Exemplo 2.1.7.

Qual o resto de \(36^{36}+41^{41}\) na divisão por \(77\text{?}\)

Solução

Inicialmente, vamos analisar separadamente as congruências:

\begin{equation*} 36^{36}\equiv x \mod 77 \quad \text{e} \quad 41^{41}\equiv y \mod 77. \end{equation*}

A fim de usar o item vii. do Teorema 2.1.3, vamos analisar as congruências módulo \(7\) e módulo \(11\text{,}\) separadamente.

1º a congruência do \(36^{36}\text{:}\)

\begin{equation*} 36\equiv 1 \mod 7 \end{equation*}

\begin{align*} 36\equiv\amp~ 3 \mod 11\\ 36^2\equiv\amp~ 9 \mod 11\\ 36^3\equiv\amp~ 27\equiv 5 \mod 11\\ 36^4\equiv\amp~ 5\cdot3\equiv 4 \mod 11\\ 36^5\equiv\amp~ 3\cdot 4\equiv 1 \mod 11 \end{align*}

Então, \(36^5\equiv 1 \mod 7\) e \(36^5\equiv 1 \mod 11\text{.}\) Assim, pelo item vii.

\begin{equation*} 36^5\equiv 1 \mod 77. \end{equation*}

Como \(36 = 5\cdot 7 +1\text{,}\) temos

\begin{equation*} 36^{36} \equiv(36^5)^7\cdot 36\equiv1\cdot 36 \equiv 36 \mod 77. \end{equation*}

2º a congruência do \(41^{41}\text{:}\)

\begin{align*} 41\equiv\amp~ 6 \mod 7\\ 41^2\equiv\amp~ 36 \equiv 1 \mod 7 \end{align*}

\begin{align*} 41\equiv\amp~ 8 \mod 11\\ 41^2\equiv\amp~ 64 \equiv 9 \equiv -2\mod 11\\ 41^4\equiv\amp~ 4 \mod 11\\ 41^5\equiv\amp~ 4\cdot 8 \equiv 32 \equiv 10 \equiv -1 \mod 11\\ 41^{10}\equiv\amp~ 1 \mod 11 \end{align*}

Então, \(41^{10}\equiv 1 \mod 7\) e \(41^{10}\equiv 1 \mod 11\text{.}\) Assim, pelo item vii.

\begin{equation*} 41^{10}\equiv 1 \mod 77. \end{equation*}

Como \(41 = 10\cdot 4 +1\text{,}\) temos

\begin{equation*} 41^{41} \equiv(41^{10})^4\cdot 41\equiv1\cdot 41 \equiv 41 \mod 77. \end{equation*}

Assim,

\begin{equation*} 36^{36}+41^{41}\equiv 36+41 \equiv 77 \equiv 0 \mod 77. \end{equation*}

Portanto, o resto é zero.

Exemplo 2.1.8.

Prove que \(p^2-1\) é divisível por \(24\) se \(p\) é um primo maior que \(3\text{.}\)

Solução

Como \(p\) é um primo ímpar, podemos escrevê-lo da seguinte maneira: \(p=2k+1\text{,}\) para algum \(k\in \mathbb{N}\text{.}\) Assim,

\begin{align*} p^2-1 =\amp~ (2k+1)^2-1\\ =\amp~ 4k^2+4k + 1-1\\ =\amp~ 4k(k+1) \end{align*}

Observe que \(8\) divide \(4k(k+1)\text{,}\) pois ou \(k\) ou \(k+1\) será par. Então,

\begin{equation*} p^2-1 \equiv 0 \mod 8. \end{equation*}

Agora, basta mostrar que \(3\) divide \(p^2-1\text{.}\) Note que

\begin{equation*} p \equiv \pm 1 \mod 3. \end{equation*}

Portanto,

\begin{align*} p^2\equiv\amp~ 1 \mod 3\\ p^2-1\equiv\amp~ 0 \mod 3 \end{align*}

Logo,

\begin{equation*} p^2-1 \equiv 0 \mod 24. \end{equation*}

Exemplo 2.1.9. (IMO).

Seja \(s(n)\) a soma dos dı́gitos de \(n\text{.}\) Se \(N = 4444^{4444}\text{,}\) \(A = s(N)\) e \(B = s(A)\text{.}\) Quanto vale \(s(B)\text{?}\)

Solução

Pelo critério de divisibilidade por \(9\text{,}\) \(N \equiv A \equiv B \mod 9\text{,}\) pois o resto da divisão de \(N\) por \(9\) é o mesmo que o resto da divisão da soma dos dígitos de \(N\) por \(9\text{.}\) Como

\begin{equation*} 4444\equiv 16\equiv 7 \mod 9, \end{equation*}

precisamos encontrar \(7^{4444} \mod 9\text{.}\)

\begin{align*} 7^2\equiv\amp~ 4 \mod 9\\ 7^3\equiv\amp~ 4\cdot 7 \equiv 1 \mod 9. \end{align*}

Como \(4444 = 1481\cdot 3+1\text{,}\) temos

\begin{equation*} 7^{4444}\equiv 7^{1481\cdot 3+1}\equiv (7^3)^{1481}\cdot 7 \equiv 7 \mod 9. \end{equation*}

Agora, vamos estimar o valor de \(s(B)\text{.}\) Como \(4444\lt 10^5\text{,}\) temos \(N=4444^{4444}\lt 10^{5\cdot 4444}\text{.}\) Então, o maior valor possível para \(s(N)\) seria se \(N\) fosse igual a \(10^{5\cdot 4444}-1\text{,}\) ou seja, \(N\) teria \(5\cdot 4444\) dígitos do número \(9\text{,}\) portanto \(A=s(N)\leq 5\cdot 4444\cdot 9=199980\text{.}\)

Além disso, \(B=s(A)\leq 1+9\cdot 5=46\text{.}\) Então, \(s(B)\) é menor ou igual a maior soma dos dígitos dos números naturais menores que \(46\text{.}\) Logo,

\begin{equation*} s(B)\leq s(46), s(45)\ldots, s(39), s(38), \ldots \end{equation*}

Como a maior soma é \(s(39)=12\text{,}\) \(s(B)\leq 12\text{.}\) O único inteiro menor ou igual a \(12\) com resto \(7\) por \(9\) é o próprio \(7\text{,}\) daí \(s(B)=7\text{.}\)

Exemplo 2.1.10.

Prove que \(11^{n+2} + 12^{2n+1}\) é divisı́vel por \(133\) para qualquer natural \(n\text{.}\)

Solução

\begin{align*} 12^2 \equiv 144 \equiv\amp~ 11 \mod 133\\ 12^2 \equiv\amp~ 11 \mod 133\\ 12^{2n}\equiv \amp~ 11^n \mod 133\\ 12^{2n+1}\equiv\amp~ 11^n\cdot 12 \mod 133\\ 12^{2n+1}\equiv\amp~ 11^n(133-121)\\ 12^{2n+1}\equiv\amp~ 11^n\cdot 133 +11^n\cdot(-121)\mod 133\\ 12^{2n+1}\equiv \amp~ -11^{n+2}\mod 133\\ 12^{2n+1} +11^{n+2}\equiv \amp~ 0\mod 133 \end{align*}

Exemplo 2.1.11.

Prove que \(n^5 + 4n\) é divisı́vel por \(5\) para todo inteiro \(n\text{.}\)

Solução

O número \(n\) só pode ser congruente ou a 0, ou a 1, ou a 2, ou a 3 ou a 4, módulo 5. Vamos analisar cada caso.

Caso \(n\equiv 0 \mod 5:\)
\begin{equation*} n^5+4n \equiv 0 \mod 5. \end{equation*}
Caso \(n\equiv 1 \mod 5:\)
\begin{equation*} n^5+4n \equiv 1^5 + 4\cdot 1 \equiv 5 \equiv 0 \mod 5. \end{equation*}
Caso \(n\equiv 2 \mod 5:\)
\begin{equation*} n^5+4n \equiv 2^5 + 4\cdot 2 \equiv 32+8 \equiv 40 \equiv 0 \mod 5. \end{equation*}
Caso \(n\equiv 3 \mod 5:\)
\begin{equation*} n^5+4n \equiv 3^5 + 4\cdot 3 \equiv 243+12 \equiv 260 \equiv 0 \mod 5. \end{equation*}
Caso \(n\equiv 4 \mod 5:\)
\begin{equation*} n^5+4n \equiv 4^5 + 4\cdot 4 \equiv 4^2(4^3+1) \equiv 4^2\cdot 65 \equiv 0 \mod 5. \end{equation*}

Exemplo 2.1.12.

Seja \(n > 6\) um inteiro positivo tal que \(n - 1\) e \(n + 1\) são primos. Mostre que \(n^2 (n^2 + 16)\) é divisível por \(720\text{.}\) A recı́proca é verdadeira?

Solução

Observe que \(n=6k\text{,}\) para algum \(k\in \mathbb{N}\text{.}\) De fato, dentre os números \(n-1, n, n+1\text{,}\) exatamente um deles é divisível por 3 e como \(n-1\) e \(n+1\) são primos, \(n\) é divisível por 3 e é par.

Substituindo \(n=6k\) em \(n^2(n^2+16)\text{:}\)

\begin{align*} n^2(n^2+16)=\amp~ (6k)^2((6k)^2+16)\\ =\amp~ 36k^2(36k^2+16)\\ =\amp~2^4\cdot 3^4\cdot k^4+2^6\cdot 3^3\cdot k^2\\ =\amp~2^4\cdot3^2(3^2k^4+2^2k^2) \end{align*}

Como \(720=2^4\cdot 3^2\cdot 5\text{,}\) basta mostrar que 5 divide \((3^2k^4+2^2k^2)\text{.}\) Vamos analisar a congruência módulo 5.

Se \(k\equiv 0 \mod 5\text{:}\)
\begin{equation*} 9\cdot 0^4+4\cdot 0^2\equiv 0 \mod 5. \end{equation*}
Se \(k\equiv 1 \mod 5\text{:}\)
\begin{equation*} n\equiv 6 \equiv 1 \mod 5 \Rightarrow n-1 \equiv 0 \mod 5, \text{ absurdo}. \end{equation*}
Se \(k\equiv 2 \mod 5\text{:}\)
\begin{equation*} 9\cdot 2^4+4\cdot 2^2\equiv 160 \equiv 0 \mod 5. \end{equation*}
Se \(k\equiv 3 \mod 5\text{:}\)
\begin{equation*} 9\cdot 3^4+4\cdot 3^2\equiv 765 \equiv 0 \mod 5. \end{equation*}
Se \(k\equiv 4 \mod 5\text{:}\)
\begin{equation*} n\equiv 6\cdot 4 \equiv 24 \equiv -1 \mod 5 \Rightarrow n+1\equiv 0\mod 5, \text{ absurdo}\text{.} \end{equation*}

Isso conclui a demonstração. A recı́proca não é verdadeira. Basta tomar, por exemplo, \(n = 90\text{,}\) pois

\begin{equation*} 90^2(90^2+16) = 65739600 = 720\cdot 91305, \end{equation*}

mas \(n+1=91=13\cdot7\text{.}\)

Teoria dos Números: notas de aula (PTOM/POTI)

Seção 2.1 Aula 03 - Congruência I

Definição 2.1.1.

Exemplo 2.1.2.

Teorema 2.1.3.

Exemplo 2.1.4.

Exemplo 2.1.5.

Exemplo 2.1.6.

Exemplo 2.1.7.

Exemplo 2.1.8.

Exemplo 2.1.9. (IMO).

Exemplo 2.1.10.

Exemplo 2.1.11.

Exemplo 2.1.12.

Exercícios 2.1.1 Exercícios