Matemática
Olá pessoal, hoje apresentarei a solução do desafio proposto anteriormente aqui blog, quer tentar resolvê-lo antes de prosseguir essa postagem? então clique aqui!
Definição: Dado um inteiro positivo $n$, dois inteiros $a$ e $b$ são congruentes módulo $n$ se a diferença $a-b$ é um múltiplo de $n$, ou seja $n|(a-b)$ ($n$ divide $a-b$), representamos a congruência como abaixo:
2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9.
- Matemática Através De Problemas - V
Olá, pessoal! Aqui vamos apresentar mais alguns problemas interessantes, e mostrar algumas soluções pros problemas propostos da ultima vez. Problemas Propostos 1 - (OMERJ-2011) Dada uma sequência de N inteiros não-negativos $a_j$ tal...
- Equações Diofantinas Exponenciais: Como O Lema De Hensel Pode Salvar Sua Vida!
Quando resolvemos problemas de teoria dos números, são muito importantes os problemas em que é dada uma equação diofantina cujas incógnitas são expoentes. Há muitas maneiras de resolver tais equações: analisar módulo algum primo conveniente,...
- Baricentro
As três medianas de um triângulo interceptam-se num mesmo ponto que divide cada mediana em duas partes tais que a parte que contém o vértice é o dobro da outra. Se $$\overline{AM_1}\text{,}\overline{BM_2}\text{,}\overline{CM_3}$$ são as medianas...
- A Reta De Euler
Quando falamos em Euler e os resultados obtidos pelo mesmo não deixamos de nos surpreender com as descobertas desse gênio da matemática, o mesmo contribuiu com a geometria plana, e ele notou que em um triângulo qualquer o Ortocentro (Encontro das...
- Teorema Da Decomposição De Polinômios
Os primeiros registros encontrados sobre a resolução de algumas equações de segundo grau são de aproximadamente $1700a.C.$ e pertence à civilizações antigas dos sumérios, egípcios e babilônios. Os gregos aperfeiçoaram a técnica de resolução...
Matemática
Aritmética Modular + Solução do Desafio "Combinando Dígitos"
Olá pessoal, hoje apresentarei a solução do desafio proposto anteriormente aqui blog, quer tentar resolvê-lo antes de prosseguir essa postagem? então clique aqui!
Antes de fornecer a resposta temos que lembrar o conceito de congruência modular.
Definição: Dado um inteiro positivo $n$, dois inteiros $a$ e $b$ são congruentes módulo $n$ se a diferença $a-b$ é um múltiplo de $n$, ou seja $n|(a-b)$ ($n$ divide $a-b$), representamos a congruência como abaixo:
$$a\equiv b\ (mod\ n)$$
Exemplos:
a) $10\equiv 1\ (mod\ 3)$, pois $10-1=9$ e $3|9$.
b) Se $n$ é ímpar, então $n^2\equiv 1\ (mod\ 2)$.
De fato, $n=2k+1$, logo $n^2=4k^2+2k+1$, assim $n^2-1=2(2k^2+k)$, portanto $2|(n^2-1)$.
Propriedades:
a) $a\equiv a\ (mod\ n)$.
De fato,
$$a-a=0\Rightarrow n|0.$$
b) Se $a\equiv b\ (mod\ n)$, então $b\equiv a\ (mod\ n)$.
Suponha que $a\equiv b\ (mod\ n)$, assim
$$n|(a-b)\Rightarrow n|(b-a)$$
Logo $b\equiv a\ (mod\ n)$.
c) Se $a\equiv b\ (mod\ n)$ e $b\equiv c\ (mod\ n)$, então $a\equiv c\ (mod\ n)$.
As duas primeiras hipóteses nos dizem que
$$n|(a-b)\quad\mbox{e}\quad n|(b-c).$$
Ora, se $n$ divide dois números, então $n$ divide a soma destes, assim
$$n|(a-b+b-c)\Rightarrow n|(a-c),$$
logo
$$a\equiv c\ (mod\ n).$$
d) Se $a\equiv b\ (mod\ n)$ e $c\equiv d\ (mod\ n)$, então $a\pm e\equiv b\pm d\ (mod\ n)$ e $ac\equiv bd\ (mod\ n)$
As duas primeiras hipóteses nos diz que
$$n|(a-b)\quad\mbox{e}\quad n|(c-d).$$
Se $n$ divide dois números, então $n$ divide a soma destes, assim
$$n|[(a-b)+(c-d)]\Rightarrow n|[(a+c)-(b+d)],$$
logo
$$a+c\equiv b+d\ (mod\ n).$$
Agora, devemos provar que $n|(ac-bd)$, assim é fácil ver que $n|c(a-b)$ e $n|b(c-d)$, usando o resultado anterior, $n$ divide a soma, logo
$$n|(ac-bc+bc-bd)\Rightarrow n|(ac-bd),$$
ou seja
$$ac\equiv bd\ (mod\ n).$$
Muitas problemas podem ser resolvidos usando congruência, em outros momentos irei explorar mais essa ferramenta aqui no blog, mas por enquanto vamos a solução do desafio.
O desafio era o seguinte:
Considere os 16 dígitos abaixo
Eles podem ser combinados de modo a criar dois números A e B de 8 dígitos cada, de modo que B=2A ?
Solução: Note inicialmente que todo número é congruente a soma de seus dígitos módulo 3.
De fato, seja podemos escrever um número em função de seus dígitos da seguinte forma:
$$n=a_0+a_1\cdot 10+a_2\cdot 10^2+\cdots+a_k\cdot 10^k,$$
onde $0\leq a_i\leq 9,\forall i\in\{0,\ldots,k\}$.
Agora
$$n-(a_0+a_1+\cdots+a_k)=\sum_{i=0}^n a_i\cdot 10^i -\sum_{i=0}^n a_i.$$
Agrupando os termos temos
$$n-(a_0+a_1+\cdots+a_k)=\sum_{i=0}^n a_i\cdot 10^i -\sum_{i=0}^n a_i.$$
Agrupando os termos temos
$$n-(a_0+a_1+\cdots+a_k)=3(3a_1+33a_2+\cdots+\underbrace{33\ldots 3}_{k\ \textrm{vezes}}).$$
Assim $n|[n-(a_0+a_1+\cdots+a_k)]$, portanto
$$n\equiv (a_0+a_1+\cdots+a_k)\ (mod\ 3).$$
Assim $n|[n-(a_0+a_1+\cdots+a_k)]$, portanto
$$n\equiv (a_0+a_1+\cdots+a_k)\ (mod\ 3).$$
Suponha agora que existissem tais números no desafio proposto.
Por um lado teríamos que
$$A+2B\equiv 2(2+\cdots+ 9)\ (mod\ 3),$$
ou seja
$$A+2B\equiv 88\ (mod\ 3),$$
mas $88\equiv 1\ (mod 3)$, logo
$$A+2B\equiv 1\ (mod 3).$$
Por outro lado, se $B=2A$, então $A+B=3A$ e como $3|3A$ isso nos diz que
$$3A\equiv 0\ (mod\ 3).$$
Absurdo, pois ambas as congruências não podem ocorrer ao mesmo tempo, logo não é possível encontrar tais números.
Vou ficando por aqui, mas em breve mostrarei mais aplicações e questões utilizando congruência, até mais!
- Matemática Através De Problemas - V
Olá, pessoal! Aqui vamos apresentar mais alguns problemas interessantes, e mostrar algumas soluções pros problemas propostos da ultima vez. Problemas Propostos 1 - (OMERJ-2011) Dada uma sequência de N inteiros não-negativos $a_j$ tal...
- Equações Diofantinas Exponenciais: Como O Lema De Hensel Pode Salvar Sua Vida!
Quando resolvemos problemas de teoria dos números, são muito importantes os problemas em que é dada uma equação diofantina cujas incógnitas são expoentes. Há muitas maneiras de resolver tais equações: analisar módulo algum primo conveniente,...
- Baricentro
As três medianas de um triângulo interceptam-se num mesmo ponto que divide cada mediana em duas partes tais que a parte que contém o vértice é o dobro da outra. Se $$\overline{AM_1}\text{,}\overline{BM_2}\text{,}\overline{CM_3}$$ são as medianas...
- A Reta De Euler
Quando falamos em Euler e os resultados obtidos pelo mesmo não deixamos de nos surpreender com as descobertas desse gênio da matemática, o mesmo contribuiu com a geometria plana, e ele notou que em um triângulo qualquer o Ortocentro (Encontro das...
- Teorema Da Decomposição De Polinômios
Os primeiros registros encontrados sobre a resolução de algumas equações de segundo grau são de aproximadamente $1700a.C.$ e pertence à civilizações antigas dos sumérios, egípcios e babilônios. Os gregos aperfeiçoaram a técnica de resolução...