Números inteiros
Sumário
1 Números Naturais
1.1 Números Inteiros
1.2 Subconjuntos de $\mathbb{Z}$
1.3 Número de divisores de $n$
1.4 Crivo de Eratóstenes
2 Critérios de divisibilidade
2.1 Divisibilidade por 2
2.2 Divisibilidade por 3
2.3 Divisibilidade por 4
2.4 Divisibilidade por 5
2.5 Divisibilidade por 6
2.6 Divisibilidade por 7
2.7 Divisibilidade por 8
2.8 Divisibilidade por 9
2.9 Divisibilidade por 10
2.10 Divisibilidade por 11
3 Congruências
3.1 Teorema chinês do resto
3.2 Exemplos
Números Naturais
Um ''número natural'' é um número não negativo $\{0,~1,~2,~\ldots\}.$ Em alguns contextos, '''número natural''' é definido como um número inteiro positivo, não sendo o zero considerado como um número natural $\{1,~2,~3,~\ldots\}.$
O conjunto dos números naturais é, comumente, denotado pelo símbolo $\mathbb{N}.$ O símbolo $\mathbb{N}^*$ é usado para explicitar que o zero não está sendo incluso, i.e. $\mathbb{N}^* = \mathbb{N}-\{0\}.$
Números inteiros:
Os
'''números inteiros''' são constituídos dos números naturais e seus simétricos
negativos, incluindo o zero. O conjunto de todos os
números inteiros é representado pela letra $\mathbb{Z}$, originada da palavra
alemã Zahlen , "números").
$\mathbb{Z}=[...-3,-2,-1,0,1,2,3...]$
Os
inteiros (juntamente com a operação de adição) formam o menor grupo que contém o monoide aditivo dos números naturais.
Como os números naturais, os inteiros formam um conjunto infinito contável.
Os
números inteiros podem ser simétricos, quando os números têm sinais opostos, ou
pode existir também o valor absoluto de um número inteiro, que é a distância
entre a origem e o número.
Subconjuntos de $\mathbb{Z}$
$\mathbb{Z}^* = $
Conjunto dos inteiros não-nulos $=\mathbb{Z}-[0]$
$\mathbb{Z}$ = Conjunto dos inteiros não negativos $=[0,1,2,3...]$
$\mathbb{Z}^* = $ Conjunto dos inteiros não negativos,
excluindo zero $=[1,2,3...]$
$\mathbb{Z} = $ Conjunto dos inteiros não positivos $=[...-3,-2,-1,0]$
$\mathbb{Z}^* = $ Conjunto dos inteiros não positivos,
excluindo zero $=[...-3,-2,-1]$
Veja que \mathbb{N} está contido em \mathbb{Z}.
Números primos e números compostos:
São aqueles que só são divisíveis por si e por 1:
${1, 2, 3, 5, 7, 11, 13, \cdots}$
Os números que não são primos são chamados de compostos. Isso porque podem ser escritos na forma:
$ n = {p_1}^{e_1}\times{p_2}^{e_2} \times {p_3}^{e_3} \times {p_4}^{e_4}\times \cdots {p_k}^{e_k}$
Onde:
$n$ é o número natural;
$p_1, p_2, p_3, \cdots p_k$ são os números primos e $e_1, e_2, e_3, \cdots e_k$ são os seus respectivos expoentes.
Exemplos:
$55000 = 2^3 \times 5^4 \times 11^1$ (ou $55000 = 2^3 \times 5^4 \times 11$);
$81 = 3^4$
etc...
$n$ tem $k$ fatores. Então ${p_k}^{e_k}$ é o $k$-ésimo fator de $n$.
Número de divisores de $n$
Divisor é o número inteiro pelo qual $n$ pode ser dividido sem deixar resto.
$n$ tem $x$ divisores, quais sejam: $ d_1, d_2, \cdots d_x$.
Onde $d_1 = 1$ e $d_x = n$. Se $n$ é primo, então $x=2$, ou seja, $1$ e $n$.
Exemplo:
Divisores de $6$:
O número $n = 6$ tem $x = 4$ divisores, quais sejam: {1, 2, 3, 6}. Veja que estamos tratando apenas dos divisores positivos.
Se $ n = {p_1}^{e_1}\times{p_2}^{e_2} \times {p_3}^{e_3} \times {p_4}^{e_4}\times \cdots {p_k}^{e_k}$
Então $x = (e_1 +1) \times (e_2+1) \times (e_3+1) \times (e_4+1) \cdots (e_k+1)$.
Exemplo:
$12 = {2^2} \times 3^{\color{red}{1}}$
O número de divisores que ele possui é $(2+1)(1+1) = 3 \times 2 = 6$.
De fato:
Os seus divisores são: $1, 2, 3, 4, 6$ e $12$.
Onde:
$n$ é o número natural;
$p_1, p_2, p_3, \cdots p_k$ são os números primos e $e_1, e_2, e_3, \cdots e_k$ são os seus respectivos expoentes.
Exemplos:
$55000 = 2^3 \times 5^4 \times 11^1$ (ou $55000 = 2^3 \times 5^4 \times 11$);
$81 = 3^4$
etc...
$n$ tem $k$ fatores. Então ${p_k}^{e_k}$ é o $k$-ésimo fator de $n$.
Número de divisores de $n$
Divisor é o número inteiro pelo qual $n$ pode ser dividido sem deixar resto.
$n$ tem $x$ divisores, quais sejam: $ d_1, d_2, \cdots d_x$.
Onde $d_1 = 1$ e $d_x = n$. Se $n$ é primo, então $x=2$, ou seja, $1$ e $n$.
Exemplo:
Divisores de $6$:
O número $n = 6$ tem $x = 4$ divisores, quais sejam: {1, 2, 3, 6}. Veja que estamos tratando apenas dos divisores positivos.
Se $ n = {p_1}^{e_1}\times{p_2}^{e_2} \times {p_3}^{e_3} \times {p_4}^{e_4}\times \cdots {p_k}^{e_k}$
Então $x = (e_1 +1) \times (e_2+1) \times (e_3+1) \times (e_4+1) \cdots (e_k+1)$.
Exemplo:
$12 = {2^2} \times 3^{\color{red}{1}}$
O número de divisores que ele possui é $(2+1)(1+1) = 3 \times 2 = 6$.
De fato:
Os seus divisores são: $1, 2, 3, 4, 6$ e $12$.
Pode servir para determinar se um número é primo ou não. O procedimento é o seguinte:
Seja $n$ um número inteiro positivo que não se sabe se é primo ou composto. Primeiro calcula-se $\sqrt n$. Se $n = d_1 \times d_2$, onde $d_1$ e $d_2$ são seus divisores positivos, então:
Se $d_1 = d_2$ então $n$ é quadrado perfeito (composto, pois $n = {d_1}^2$).
Se $d_1 < d_2$, então $d_1 < \sqrt n$ e $d_2 > \sqrt n$.
A estratégia é dividir $n$ por cada um de seus divisores menores que $\sqrt n$, para poupar trabalho. Se nenhuma dessas divisões resultar em um número inteiro, então $n$ é primo.
Exemplos:
1) Verifique se $117$ é primo.
Como $11>\sqrt {117}>10 $, pois $10^2 = 100$ e $11^2 = 121$, então basta ver se $117$ é divisível por $2$ ou $3$ ou $5$ ou $7$, que são os números primos menores que $\sqrt {117}$.
Concluímos facilmente que esse número não é primo, pois $117 = {3^2}\times 13$. Ou seja, ele é composto.
2) Verifique se $2017$ é primo.
$\sqrt {2017} = 44,9110...$. Então temos que testar todos os números primos menores que $44$.
Ou seja, por cada número do conjunto ${\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43\}}$.
Nenhuma dessas divisões resulta em um número inteiro. Logo, $2017$ é primo.
3) A questão a seguir caiu na XLIII Olimpíada Internacional de Matemática.
Seja $n$ inteiro maior que $1$. Os divisores positivos de n são $d_1,~d_2~\cdots, d_k$ onde
$1=d_1<d_2< \cdots<d_k=n$.
Seja $D={d_1}{d_2}+{d_2}{d_3}+\cdots +{d_{k-1}}{d_k}$.
a) Prove que $D<n^2$
b) Encontre todos os valores de $n$ para os quais $D$ é um divisor de $n^2$.
Solução:
a)
Seja $d_i=\frac{n}{d_{k+1-i}}$
Observando que se $d$ é divisor de $n$, então $\frac{n}{d}$ também o é, podemos agrupar os divisores aos pares, da onde concluímos que $d_i{d_{k+1-i}}=n$, com $0 \le i \le k$.
Isso também vale para o caso de $n$ ser quadrado perfeito, pois $d_{\frac{k+1}{2}}=d_{k+1-\frac{k+1}{2}}=\sqrt{n}$.
Então $d_i \le \frac{n}{k+1-i}$.
De fato, sendo $d_{k+1-i}$ o (k+1-i)-ésimo divisor de $n$, temos $d_{k+1-i} \ge k+1-i$ e, logo:
$D={d_1}{d_2}+{d_2}{d_3}+\cdots +{d_{k-1}}{d_k} \le \frac{n}{k}\cdot \frac{n}{k-1}+\frac{n}{k-1}\cdot \frac{n}{k-2}+\cdots +\frac{n}{2}\cdot \frac{n}{1} = {n^2} \displaystyle \sum_{j=1}^{k-1}\bigg(\frac{1}{j}- \frac{1}{j+1} \bigg)={n^2}\displaystyle \sum_{j=1}^{k-1} \bigg( \frac{1}{j}-\frac{1}{j+1}\bigg) = {n^2}\bigg(1-\frac{1}{k} \bigg)<n^2$.
b)
Veja que se $n$ é primo, $D=1 \times n$, e assim temos que $D$ divide $n^2$. Suponha $n$ composto, e seja $p$ o seu menor fator primo.
Como $D={d_1}{d_2}+{d_2}{d_3}+\cdots +{d_{k-1}}{d_k} = 1 \times p + \cdots + \frac{n}{p}\times n> \frac{n^2}{p}$.
Veja então que $\frac{n^2}{p}<D<n^2$, e como $\frac{n^2}{p}$ é o maior divisor de $n^2$ menor que $n^2$, concluímos que $D \nmid n^2$. ($D$ não divide $n^2$).
O conjunto dos números primos é infinito, como você pode ver aqui.
Se $d_1 = d_2$ então $n$ é quadrado perfeito (composto, pois $n = {d_1}^2$).
Se $d_1 < d_2$, então $d_1 < \sqrt n$ e $d_2 > \sqrt n$.
A estratégia é dividir $n$ por cada um de seus divisores menores que $\sqrt n$, para poupar trabalho. Se nenhuma dessas divisões resultar em um número inteiro, então $n$ é primo.
Exemplos:
1) Verifique se $117$ é primo.
Como $11>\sqrt {117}>10 $, pois $10^2 = 100$ e $11^2 = 121$, então basta ver se $117$ é divisível por $2$ ou $3$ ou $5$ ou $7$, que são os números primos menores que $\sqrt {117}$.
Concluímos facilmente que esse número não é primo, pois $117 = {3^2}\times 13$. Ou seja, ele é composto.
2) Verifique se $2017$ é primo.
$\sqrt {2017} = 44,9110...$. Então temos que testar todos os números primos menores que $44$.
Ou seja, por cada número do conjunto ${\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43\}}$.
Nenhuma dessas divisões resulta em um número inteiro. Logo, $2017$ é primo.
3) A questão a seguir caiu na XLIII Olimpíada Internacional de Matemática.
Seja $n$ inteiro maior que $1$. Os divisores positivos de n são $d_1,~d_2~\cdots, d_k$ onde
$1=d_1<d_2< \cdots<d_k=n$.
Seja $D={d_1}{d_2}+{d_2}{d_3}+\cdots +{d_{k-1}}{d_k}$.
a) Prove que $D<n^2$
b) Encontre todos os valores de $n$ para os quais $D$ é um divisor de $n^2$.
Solução:
a)
Seja $d_i=\frac{n}{d_{k+1-i}}$
Observando que se $d$ é divisor de $n$, então $\frac{n}{d}$ também o é, podemos agrupar os divisores aos pares, da onde concluímos que $d_i{d_{k+1-i}}=n$, com $0 \le i \le k$.
Isso também vale para o caso de $n$ ser quadrado perfeito, pois $d_{\frac{k+1}{2}}=d_{k+1-\frac{k+1}{2}}=\sqrt{n}$.
Então $d_i \le \frac{n}{k+1-i}$.
De fato, sendo $d_{k+1-i}$ o (k+1-i)-ésimo divisor de $n$, temos $d_{k+1-i} \ge k+1-i$ e, logo:
$D={d_1}{d_2}+{d_2}{d_3}+\cdots +{d_{k-1}}{d_k} \le \frac{n}{k}\cdot \frac{n}{k-1}+\frac{n}{k-1}\cdot \frac{n}{k-2}+\cdots +\frac{n}{2}\cdot \frac{n}{1} = {n^2} \displaystyle \sum_{j=1}^{k-1}\bigg(\frac{1}{j}- \frac{1}{j+1} \bigg)={n^2}\displaystyle \sum_{j=1}^{k-1} \bigg( \frac{1}{j}-\frac{1}{j+1}\bigg) = {n^2}\bigg(1-\frac{1}{k} \bigg)<n^2$.
b)
Veja que se $n$ é primo, $D=1 \times n$, e assim temos que $D$ divide $n^2$. Suponha $n$ composto, e seja $p$ o seu menor fator primo.
Como $D={d_1}{d_2}+{d_2}{d_3}+\cdots +{d_{k-1}}{d_k} = 1 \times p + \cdots + \frac{n}{p}\times n> \frac{n^2}{p}$.
Veja então que $\frac{n^2}{p}<D<n^2$, e como $\frac{n^2}{p}$ é o maior divisor de $n^2$ menor que $n^2$, concluímos que $D \nmid n^2$. ($D$ não divide $n^2$).
O conjunto dos números primos é infinito, como você pode ver aqui.
=====================================================================
Critérios de divisibilidade
Também podem ajudar para se determinar se um número é divisível por outro ou, ainda, se ele é primo ou não.
Divisibilidade por $2$
Um número inteiro é divisível por $2$ se for par, ou seja, se o seu último algarismo for $0$, $2$, $4$, $6$, $8$. Exemplos: $10$, $46$, $1000$,$...$. O único resto possível na divisão por $2$ é $1$, quando o número for ímpar.
Divisibilidade por $3$
Um número é divisível por $3$ se a soma de seus algarismos for divisível por 3.
Exemplos:
1) A soma dos algarismos de $5682$ é $5+6+8+2 = 21$. Logo $5682$ é divisível por $3$, pois $21 = 3 \times 7$.
2) O resto da divisão de $85$ por $3$ é $1$, pois a soma dos algarismos de $85$, que é $8+5 = 13$ deixa resto $1$ na divisão por $3$. Os restos possíveis na divisão por $3$ são $1$ e $2$.
De um modo geral, os restos possíveis na divisão por $k$ podem ser qualquer número entre $0$ e $k-1$.
Divisibilidade por $4$:
Critérios de divisibilidade
Também podem ajudar para se determinar se um número é divisível por outro ou, ainda, se ele é primo ou não.
Divisibilidade por $2$
Um número inteiro é divisível por $2$ se for par, ou seja, se o seu último algarismo for $0$, $2$, $4$, $6$, $8$. Exemplos: $10$, $46$, $1000$,$...$. O único resto possível na divisão por $2$ é $1$, quando o número for ímpar.
Divisibilidade por $3$
Um número é divisível por $3$ se a soma de seus algarismos for divisível por 3.
Exemplos:
1) A soma dos algarismos de $5682$ é $5+6+8+2 = 21$. Logo $5682$ é divisível por $3$, pois $21 = 3 \times 7$.
2) O resto da divisão de $85$ por $3$ é $1$, pois a soma dos algarismos de $85$, que é $8+5 = 13$ deixa resto $1$ na divisão por $3$. Os restos possíveis na divisão por $3$ são $1$ e $2$.
De um modo geral, os restos possíveis na divisão por $k$ podem ser qualquer número entre $0$ e $k-1$.
Divisibilidade por $4$:
Um número é divisível por 4 se o número formado pelos dois últimos algarismos for divisível por $4$. Se o último algarismo for ímpar, então não é divisível.
Se o último algarismo for 0, 4 ou 8, então o penúltimo algarismo deve ser par.
Se o último algarismo for 2 ou 6, então o penúltimo algarismo deve ser ímpar.
Por exemplo 543416 é divisível por $4$, pois o número formado pelos dois últimos algarismos ($16$) é divisível por $4$).
Divisibilidade por$5$
Um número é divisível por $5$ se o último algarismo for $0$ ou $5$
Divisibilidade por $6$
Um número é divisível por $6$ se for, ao mesmo tempo, divisível por $2$ e por $3$.
Generalizando, um número é divisível por $a, b, c, ...$, então ele é divisível pelo produto desses fatores.
Divisibilidade por $7$
Observe:
Vamos ver se $96578235408$ é divisível por $7$.
Separe os números formados pelas classes de algarismos, de 3 em 3:
Os três últimos algarismos formam $408$ (classe $1$).
A classe anterior é $235$ (classe $2$).
A classe anterior é $578$ (classe $3$
A anterior a essa é $\color{blue}{0}96$ (classe $4$).
Soma das classes ímpares: $408 + 578 = 986$.
Soma das classes pares: $235+96 = 331$
Diferença entre as classes pares e as ímpares (o maior número menos o menor número):
$986-331 = 655$.
Se $655$ for divisível por $7$, então $96578235408$ também é.
Ocorre que $655$ não é divisível por $7$, pois deixa resto $4$.
O que significa que $96578235408$ também deixa resto $4$ na divisão por $7$.
Divisibilidade por $8$
Um número é divisível por $8$ se o número formado pelos $3$ últimos algarismos também for divisível por $8$.
Generalizando, para $k$ suficientemente grande, um número é divisível por $2^k$ se o número formado pelos $k$ últimos algarismos for divisível por $2^k$.
Divisibilidade por $9$
De modo semelhante ao critério de divisibilidade por $3$, um número é divisível por $9$ se a soma de seus algarismos for divisível por $9$.
Divisibilidade por $10$
Um número é divisível por $10$ se for, simultaneamente, divisível por $2$ e por $5$ (pois $2 \times 5 = 10$).
Para ser divisível por $5$ tem que terminar em $0$ ou $5$.
Para ser divisível por $2$, tem que terminar em $0$ ou $2$ ou $4$ ou $6$ ou $8$.
Concluindo, para ser divisível por $10$ é necessário que o último algarismo seja $0$.
Divisibilidade por 11
De modo semelhante ao critério de divisibilidade por $7$, dessa vez vamos separar o número em classes de $1$ em $1$. Tomemos então o número $96578235408$.
Soma das classes ímpares: $8+4+3+8+5+9 = 37$.
Soma das classes pares: $0+5+2+7+6 = 20$.
Diferença do maior número menos o menor: $37 - 20 = 17$.
Ocorre que $17$ não é divisível por $11$ pois deixa resto $6$. O que significa que $96578235408$ também deixa resto $6$ na divisão por $11$.
=======================================================================
Diz-se que a é congruente a b módulo m se m|(a - b). (Se (a-b) é divisível por m).
Usamos como símbolo de a congruente a b modulo m :.
Usamos como símbolo de a congruente a b modulo m :.
- Se então existe um inteiro $k$ tal que $a = b + km$.
- Sempre ;
- Se , então: ;
- Se e , então: ;
- Se e , então
- Se , então: , onde c é um inteiro;
- Se , então: , onde c é um inteiro;
- Se , então: , onde c é um inteiro;
- Se e , então: ;
- Se e , então: ;
- Se e , então: ;
- Se , então: , onde d é o máximo divisor comum de $c$ e $m$.
Sendo $a$, $b$, $c$ e $n$ números inteiros e $a \equiv b (\mod c)$ , então $\displaystyle a^n \equiv b^n (\mod c)$.
Pois $ \displaystyle a^n - b^n $ é divisível por $a - b$. Vou escrever sobre isso em outra postagem.
$X = {a_1}{M_1}{x_1} + {a_2}{M_2}{x_2} + \cdots + {a_n}{M_n}{x_n}$ $M_a$ é o produto de todos os $m_k$ com exceção de $m_a$.
Exemplo: $M_1={m_2}{\cdot}{m_3}{\cdots}{m_n}$ $x_a$ é o número que torna $M_a{\cdot}{x_a} \equiv 1 \pmod{m_a}$
Exemplos
1)
$x \equiv 3 \pmod{5}$
$x \equiv 5 \pmod{13}$
$x \equiv 7 \pmod{29}$
$x \equiv 1 \pmod{41}$
_______________________________________________________________________
$X = 3{\cdot}13{\cdot}29{\cdot}41{\cdot}x_1 + 5{\cdot}5{\cdot}29{\cdot}41{\cdot}x_2 + 7{\cdot}5{\cdot}13{\cdot}41{\cdot}x_3 + 1{\cdot}5{\cdot}13{\cdot}29{\cdot}x_4$.
Lembre que se $p_1$, $p_2$ forem inteiros e ${x_1}{x_2} \equiv a \pmod{b}$, então $(x_1 - y_1) = {p_1}{\cdot}{x_1}$ e $(x_2 - y_2) = {p_2}{\cdot}{x_2} \leftrightarrow {x_1}{x_2} \equiv {y_1}{y_2} \pmod{b}.$
Isso é muito fácil de demonstrar: $({p_1}x_1 - y_1)({p_2}x_2 - y_2) = {p_1}{p_2}{x_1}{x_2}-{y_2}{p_1}{x_1}-{y_1}{p_2}{x_2}+{y_1}{y_2} \equiv {y_1}{y_2} \pmod{b}$.
(É só generalizar para o caso de haver mais fatores no produto).
$x_1{\cdot}13{\cdot}29{\cdot}41 \equiv 1\pmod{5} \rightarrow x_1{\cdot}(-2){\cdot}(-1){\cdot}(1) \equiv x_1{\cdot}2 \equiv 1\pmod{5}$.
$x_1 \equiv 3 \pmod{5}$
Observe que $6 \equiv 1 \pmod{5}$, então $2{\cdot}x_1=6 \rightarrow x_1 = 3.$
$x_2{\cdot}5{\cdot}29{\cdot}41 \equiv 1 \pmod{13} \rightarrow x_2{\cdot}5{\cdot}3{\cdot}2 \equiv 1 \pmod{13} \rightarrow x_2{\cdot}4 \equiv 1 \pmod{13}$
$x_2 \equiv 10 \pmod{13}$
Observe que $40 \equiv 1 \pmod{13}$, então $4{\cdot}x_2=40 \rightarrow x_2 = 10.$
$x_3{\cdot}5{\cdot}13{\cdot}41 \equiv 1 \pmod{29} \rightarrow x_3{\cdot}5{\cdot}13{\cdot}17 \equiv 1 \pmod{29} \rightarrow x_3{\cdot}3 \equiv 1 \pmod{29}$
$x_3 \equiv {-10} \pmod{29}$
$x_4{\cdot}5{\cdot}13{\cdot}29 \equiv 1 \pmod{41} \rightarrow x_4{\cdot}5{\cdot}13{\cdot}(-12) \equiv 1 \pmod{41} \rightarrow {x_4}{\cdot}{(-1)} \equiv 1 \pmod{41}$
$x_4\equiv{-1} \pmod{41}$
$X=3{\cdot}13{\cdot}29{\cdot}41{\cdot}3 + 5{\cdot}5{\cdot}29{\cdot}41{\cdot}10 + 7{\cdot}5{\cdot}13{\cdot}41{\cdot}(-10) + 1{\cdot}5{\cdot}13{\cdot}29{\cdot}(-1)$
$X=139113 + 297250 – 186550 -1885$
$X=247928$
$x \equiv X \equiv 247928 \pmod{5{\cdot}13{\cdot}29{\cdot}41} \rightarrow x \equiv 16073 \pmod{77285}$
$x \equiv 16073 \pmod{77285}$
De fato:
$16073 \equiv 3 \pmod{5}$
$16073 \equiv 5 \pmod{13}$
$16073 \equiv 7 \pmod{29}$
$16073 \equiv 1 \pmod{41}$
______________________________________________________________________
2)
A questão abaixo foi retirada de um concurso para Técnico Judiciário realizado em 2014 pela Universidade Federal do Paraná:
Uma caixa contém certa quantidade de lâmpadas. Ao retirá-las de 3 em 3 ou de 5 em 5, sobram 2 lâmpadas na caixa.
Entretanto, se as lâmpadas forem removidas de 7 em 7, sobrará uma única lâmpada. Assinale a alternativa
correspondente à quantidade de lâmpadas que há na caixa, sabendo que esta comporta um máximo de 100 lâmpadas.
Neste caso poderíamos fazer por tentativas, mas isso se tornaria inviável para o caso de a questão envolver números muito grandes. Então vamos fazer o sistema de congruências lineares, com os dados da questão. Seja $x$ o número de lâmpadas procurado. Então:
$x \equiv 2 \pmod{3}$
$x \equiv 2 \pmod{5}$
$x \equiv 1 \pmod{7}$
$x<100$
$X=2{\cdot}5{\cdot}7{\cdot}x_1+ 2{\cdot}3{\cdot}7{\cdot}x_2+1{\cdot}3{\cdot}5{\cdot}x_3$
$5{\cdot}7{\cdot}x_1 \equiv 1 \pmod{3} \rightarrow 35x_1 \equiv 1 \pmod{3}$
$x_1 \equiv 1\pmod{3}$, pois $70 \equiv 1 \pmod{3}$
$21{\cdot}x_2 \equiv 1 \pmod{5} \rightarrow x_2 \equiv 1 \pmod{5}$
$15x_3 \equiv 1 \pmod{7} \rightarrow x_3 \equiv 1 \pmod{7}$
$X=2{\cdot}5{\cdot}7{\cdot}(2) + 2{\cdot}3{\cdot}7{\cdot}(1)+ (1){\cdot}3{\cdot}5{\cdot}(1)$
$X=140+42+15 = 197$
$x \equiv X \equiv 197 \pmod{3{\cdot}5{\cdot}7} \rightarrow x \equiv 197 \pmod {105}$
$x \equiv 197 \pmod{105} \rightarrow x \equiv 92 \pmod{105}$.
$x \equiv 92 \pmod{105}$
Então, temos que $92$ é o menor inteiro positivo que satisfaz o sistema de congruências e é a resposta para a questão.
Você também pode resolver sistemas de congruências lineares online no site https://www.dcode.fr/chinese-remainder
Se $m_k$ é um inteiro positivo e $mdc(m_i,m_j) = 1 (i ≠ j)$ (números primos entre si) então o sistema de congruências lineares:
$x \equiv a_1 \pmod{m_1}$
$x \equiv a_2 \pmod{m_2}$
$\cdots$
$x \equiv a_{n-1} \pmod{m_{n-1}}$
$x \equiv a_{n-1} \pmod{m_{n-1}}$
$x \equiv a_{n} \pmod{m_{n}}$
Tem uma única solução:
$x \equiv X \pmod{m} $
$ m= {m_1}{m_2}{m_3}{\cdots}{m_{n-1}}{m_{n}}$
$x \equiv X \pmod{m} $
$ m= {m_1}{m_2}{m_3}{\cdots}{m_{n-1}}{m_{n}}$
O valor de $X$ pode ser encontrado utilizando-se o Teorema do Resto Chinês:
$X = {a_1}{M_1}{x_1} + {a_2}{M_2}{x_2} + \cdots + {a_n}{M_n}{x_n}$ $M_a$ é o produto de todos os $m_k$ com exceção de $m_a$.
Exemplo: $M_1={m_2}{\cdot}{m_3}{\cdots}{m_n}$ $x_a$ é o número que torna $M_a{\cdot}{x_a} \equiv 1 \pmod{m_a}$
Exemplos
1)
$x \equiv 3 \pmod{5}$
$x \equiv 5 \pmod{13}$
$x \equiv 7 \pmod{29}$
$x \equiv 1 \pmod{41}$
_______________________________________________________________________
$X = 3{\cdot}13{\cdot}29{\cdot}41{\cdot}x_1 + 5{\cdot}5{\cdot}29{\cdot}41{\cdot}x_2 + 7{\cdot}5{\cdot}13{\cdot}41{\cdot}x_3 + 1{\cdot}5{\cdot}13{\cdot}29{\cdot}x_4$.
Lembre que se $p_1$, $p_2$ forem inteiros e ${x_1}{x_2} \equiv a \pmod{b}$, então $(x_1 - y_1) = {p_1}{\cdot}{x_1}$ e $(x_2 - y_2) = {p_2}{\cdot}{x_2} \leftrightarrow {x_1}{x_2} \equiv {y_1}{y_2} \pmod{b}.$
Isso é muito fácil de demonstrar: $({p_1}x_1 - y_1)({p_2}x_2 - y_2) = {p_1}{p_2}{x_1}{x_2}-{y_2}{p_1}{x_1}-{y_1}{p_2}{x_2}+{y_1}{y_2} \equiv {y_1}{y_2} \pmod{b}$.
(É só generalizar para o caso de haver mais fatores no produto).
$x_1{\cdot}13{\cdot}29{\cdot}41 \equiv 1\pmod{5} \rightarrow x_1{\cdot}(-2){\cdot}(-1){\cdot}(1) \equiv x_1{\cdot}2 \equiv 1\pmod{5}$.
$x_1 \equiv 3 \pmod{5}$
Observe que $6 \equiv 1 \pmod{5}$, então $2{\cdot}x_1=6 \rightarrow x_1 = 3.$
$x_2{\cdot}5{\cdot}29{\cdot}41 \equiv 1 \pmod{13} \rightarrow x_2{\cdot}5{\cdot}3{\cdot}2 \equiv 1 \pmod{13} \rightarrow x_2{\cdot}4 \equiv 1 \pmod{13}$
$x_2 \equiv 10 \pmod{13}$
Observe que $40 \equiv 1 \pmod{13}$, então $4{\cdot}x_2=40 \rightarrow x_2 = 10.$
$x_3{\cdot}5{\cdot}13{\cdot}41 \equiv 1 \pmod{29} \rightarrow x_3{\cdot}5{\cdot}13{\cdot}17 \equiv 1 \pmod{29} \rightarrow x_3{\cdot}3 \equiv 1 \pmod{29}$
$x_3 \equiv {-10} \pmod{29}$
$x_4{\cdot}5{\cdot}13{\cdot}29 \equiv 1 \pmod{41} \rightarrow x_4{\cdot}5{\cdot}13{\cdot}(-12) \equiv 1 \pmod{41} \rightarrow {x_4}{\cdot}{(-1)} \equiv 1 \pmod{41}$
$x_4\equiv{-1} \pmod{41}$
$X=3{\cdot}13{\cdot}29{\cdot}41{\cdot}3 + 5{\cdot}5{\cdot}29{\cdot}41{\cdot}10 + 7{\cdot}5{\cdot}13{\cdot}41{\cdot}(-10) + 1{\cdot}5{\cdot}13{\cdot}29{\cdot}(-1)$
$X=139113 + 297250 – 186550 -1885$
$X=247928$
$x \equiv X \equiv 247928 \pmod{5{\cdot}13{\cdot}29{\cdot}41} \rightarrow x \equiv 16073 \pmod{77285}$
$x \equiv 16073 \pmod{77285}$
De fato:
$16073 \equiv 3 \pmod{5}$
$16073 \equiv 5 \pmod{13}$
$16073 \equiv 7 \pmod{29}$
$16073 \equiv 1 \pmod{41}$
______________________________________________________________________
2)
A questão abaixo foi retirada de um concurso para Técnico Judiciário realizado em 2014 pela Universidade Federal do Paraná:
Uma caixa contém certa quantidade de lâmpadas. Ao retirá-las de 3 em 3 ou de 5 em 5, sobram 2 lâmpadas na caixa.
Entretanto, se as lâmpadas forem removidas de 7 em 7, sobrará uma única lâmpada. Assinale a alternativa
correspondente à quantidade de lâmpadas que há na caixa, sabendo que esta comporta um máximo de 100 lâmpadas.
Neste caso poderíamos fazer por tentativas, mas isso se tornaria inviável para o caso de a questão envolver números muito grandes. Então vamos fazer o sistema de congruências lineares, com os dados da questão. Seja $x$ o número de lâmpadas procurado. Então:
$x \equiv 2 \pmod{3}$
$x \equiv 2 \pmod{5}$
$x \equiv 1 \pmod{7}$
$x<100$
$X=2{\cdot}5{\cdot}7{\cdot}x_1+ 2{\cdot}3{\cdot}7{\cdot}x_2+1{\cdot}3{\cdot}5{\cdot}x_3$
$5{\cdot}7{\cdot}x_1 \equiv 1 \pmod{3} \rightarrow 35x_1 \equiv 1 \pmod{3}$
$x_1 \equiv 1\pmod{3}$, pois $70 \equiv 1 \pmod{3}$
$21{\cdot}x_2 \equiv 1 \pmod{5} \rightarrow x_2 \equiv 1 \pmod{5}$
$15x_3 \equiv 1 \pmod{7} \rightarrow x_3 \equiv 1 \pmod{7}$
$X=2{\cdot}5{\cdot}7{\cdot}(2) + 2{\cdot}3{\cdot}7{\cdot}(1)+ (1){\cdot}3{\cdot}5{\cdot}(1)$
$X=140+42+15 = 197$
$x \equiv X \equiv 197 \pmod{3{\cdot}5{\cdot}7} \rightarrow x \equiv 197 \pmod {105}$
$x \equiv 197 \pmod{105} \rightarrow x \equiv 92 \pmod{105}$.
$x \equiv 92 \pmod{105}$
Então, temos que $92$ é o menor inteiro positivo que satisfaz o sistema de congruências e é a resposta para a questão.
Você também pode resolver sistemas de congruências lineares online no site https://www.dcode.fr/chinese-remainder
Comentários
Postar um comentário