Divisor de 111...11
484 views
Skip to first unread message
Sergio Alvarez
Oct 22, 2009, 8:26:46 PM10/22/09
to matematic...@googlegroups.com
Seja n um inteiro positivo que não seja múltiplo de 2 nem de 5. Prove que n possui um múltiplo da forma 111...11.
Por exemplo, 37 é divisor de 111, 101 é divisor de 1111, 41 é divisor de 11111.
Pois é galera, agora é que a gente vai ver com quantos 1's se faz um múltiplo de 17...
Por exemplo, 37 é divisor de 111, 101 é divisor de 1111, 41 é divisor de 11111.
Pois é galera, agora é que a gente vai ver com quantos 1's se faz um múltiplo de 17...
Cristiano Santos Benjamin
Oct 22, 2009, 9:33:17 PM10/22/09
to Matemática Radical
Bom... pensei bastante aqui, tentei fazer alguma coisas mas sem
nenhuma ideia que me fizesse resolver o problema.
A primeira coisa que fiz foi escrever n como o produto de primos. Mas
não me levou a nada. Depois Resolvi supor que exista um n onde o 2 e o
5 não o divida e que todo múltimplo de n tem ao menos um algarismo
diferente de 1. Também não cheguei a lugar nenhum. Vou ver se eu sonho
com a resolução.. rs
Amanhã eu tento mais aguma coisa
nenhuma ideia que me fizesse resolver o problema.
A primeira coisa que fiz foi escrever n como o produto de primos. Mas
não me levou a nada. Depois Resolvi supor que exista um n onde o 2 e o
5 não o divida e que todo múltimplo de n tem ao menos um algarismo
diferente de 1. Também não cheguei a lugar nenhum. Vou ver se eu sonho
com a resolução.. rs
Amanhã eu tento mais aguma coisa
Cristiano Santos Benjamin
Oct 23, 2009, 11:33:00 AM10/23/09
to Matemática Radical
Segue outra maneira de reformular o problema. Talvez isso possa trazer
alguma idéia legal pra algum de vocês. Mas pra mim até agora nada.
Seja n:=a(k-1)a(k-2)...a0 onde os a(i) são os algarismos do número n e
seja w=111...11 o menor número que seja maior ou igual a n.
Façamos a diferença:
w-n=[10-a(k-1)][10-a(k-2))]..[10-a1][11-a0] onde cada [] é um
algarismo desse novo número e vamos chamar esse número de z.
Sendo assim o problema se resume a mostrar que ou z é múltiplo de n ou
existe um t>k tal que 10^t+10^(t-1)+...+10^(k+1)+z seja múltiplo de n.
Talvez a solução passe longe disso, mas estou tentando enchergar o
problema de todos os angulos possíveis. Se isso der alguma ideia legal
pra alguém bom, se não, vamos pensar em outro caminho.
On Oct 22, 10:33 pm, Cristiano Santos Benjamin
> > múltiplo de 17...- Hide quoted text -
>
> - Show quoted text -
alguma idéia legal pra algum de vocês. Mas pra mim até agora nada.
Seja n:=a(k-1)a(k-2)...a0 onde os a(i) são os algarismos do número n e
seja w=111...11 o menor número que seja maior ou igual a n.
Façamos a diferença:
w-n=[10-a(k-1)][10-a(k-2))]..[10-a1][11-a0] onde cada [] é um
algarismo desse novo número e vamos chamar esse número de z.
Sendo assim o problema se resume a mostrar que ou z é múltiplo de n ou
existe um t>k tal que 10^t+10^(t-1)+...+10^(k+1)+z seja múltiplo de n.
Talvez a solução passe longe disso, mas estou tentando enchergar o
problema de todos os angulos possíveis. Se isso der alguma ideia legal
pra alguém bom, se não, vamos pensar em outro caminho.
On Oct 22, 10:33 pm, Cristiano Santos Benjamin
>
> - Show quoted text -
Sergio Alvarez
Oct 23, 2009, 11:53:12 AM10/23/09
to matematic...@googlegroups.com
Dica 1: O que você ganha considerando os restos dos números da forma 11...1 na divisão por n?
2009/10/23 Cristiano Santos Benjamin <csbenja...@hotmail.com>
Cristiano Santos Benjamin
Oct 24, 2009, 3:20:25 AM10/24/09
to Matemática Radical
Olá pessoal!!
Mesmo com a dica de Sérgio deu muito trabalho demonstrar. Pensei no
problema boa parte do dia e antes de dormir eu consultei um livro de
aritimética para ver as propriedades das congruencias modulo m. E uma
que me chamou a atenção foi que "a" é congruente a "b" modulo m se e
somente se m divide |a-b|. Lembrando que dizer que "a" é congruente a
"b" modulo m significa que "a" dividido por m e "b" dividido por m
deixam o mesmo resto. Caso deixam restos diferentes dizemos que eles
não são congruentes modulo m e portanto m não divide |a-b|. Quando
estava deitado pra dormir resolvi pensar mais um pouco e me veio a
solução. Aí vim correndo escrever. Caso fique alguma dúvida pela
notação ou por alguma outra coisa podem perguntar.
Seja m o número em questão. Vamos considerar a sequência a_(n)=
(1,11,111,1111,…). Seja r_(n) uma nova sequencia tal que r_(i)=a_(i)
%m, ou seja, o resto da divisão de a_(i) por m. Se algum r_(i) for 0
então teremos que a_(i) é múltiplo de m. Vamos supor que r_(i) seja
diferente de 0 para todo i<=k,para algum k pertencente aos naturais.
Seja r_(i) e r_(j) restos com i<j<=k. Temos que a_(j) - a_(i) = a_(j-
i) * 10^i. Facilmente verificamos que m não divide essa diferença,
pois como pela hipótese 10^i e m são primos entre si, pra dividir ele
teria que dividir a_(j-i) e a divisão de a_(j-i) por m deixa resto
diferente de 0 pelo fato de j-i ser menor que k (hipótese). Essa
diferença não ser divisível por m implica que a_(i) não é congruente a
a_(j), modulo m. Logo todos os r_(i) em questão são dois a dois
distintos. Temos também que r_(i) pertence a {0,1,2,3,...,m-1}. Então
se fizermos k=m, algum dos r_i será igual a 0, e portanto a_(i) será
múltiplo de m. cqd
Podemos também verificar facilmente se r_(i)=0 então r_(i+1)=r_(2), r_
(i+2)=r_(2), r_(i+3)=r_(3), ... E em particular r_(i)=r_(wi)=0 para
todo w pertencentes os naturais. Logo m possui infinitos múltiplos da
forma 111...11.
É isso. Espero que esteja certo. Caso tenha algum erro me informem.
Abraço a todos
On Oct 23, 12:53 pm, Sergio Alvarez <sergio1...@gmail.com> wrote:
> Dica 1: O que você ganha considerando os restos dos números da forma 11...1
> na divisão por n?
>
> 2009/10/23 Cristiano Santos Benjamin <csbenjamin.m...@hotmail.com>
> > > - Show quoted text -- Hide quoted text -
Mesmo com a dica de Sérgio deu muito trabalho demonstrar. Pensei no
problema boa parte do dia e antes de dormir eu consultei um livro de
aritimética para ver as propriedades das congruencias modulo m. E uma
que me chamou a atenção foi que "a" é congruente a "b" modulo m se e
somente se m divide |a-b|. Lembrando que dizer que "a" é congruente a
"b" modulo m significa que "a" dividido por m e "b" dividido por m
deixam o mesmo resto. Caso deixam restos diferentes dizemos que eles
não são congruentes modulo m e portanto m não divide |a-b|. Quando
estava deitado pra dormir resolvi pensar mais um pouco e me veio a
solução. Aí vim correndo escrever. Caso fique alguma dúvida pela
notação ou por alguma outra coisa podem perguntar.
Seja m o número em questão. Vamos considerar a sequência a_(n)=
(1,11,111,1111,…). Seja r_(n) uma nova sequencia tal que r_(i)=a_(i)
%m, ou seja, o resto da divisão de a_(i) por m. Se algum r_(i) for 0
então teremos que a_(i) é múltiplo de m. Vamos supor que r_(i) seja
diferente de 0 para todo i<=k,para algum k pertencente aos naturais.
Seja r_(i) e r_(j) restos com i<j<=k. Temos que a_(j) - a_(i) = a_(j-
i) * 10^i. Facilmente verificamos que m não divide essa diferença,
pois como pela hipótese 10^i e m são primos entre si, pra dividir ele
teria que dividir a_(j-i) e a divisão de a_(j-i) por m deixa resto
diferente de 0 pelo fato de j-i ser menor que k (hipótese). Essa
diferença não ser divisível por m implica que a_(i) não é congruente a
a_(j), modulo m. Logo todos os r_(i) em questão são dois a dois
distintos. Temos também que r_(i) pertence a {0,1,2,3,...,m-1}. Então
se fizermos k=m, algum dos r_i será igual a 0, e portanto a_(i) será
múltiplo de m. cqd
Podemos também verificar facilmente se r_(i)=0 então r_(i+1)=r_(2), r_
(i+2)=r_(2), r_(i+3)=r_(3), ... E em particular r_(i)=r_(wi)=0 para
todo w pertencentes os naturais. Logo m possui infinitos múltiplos da
forma 111...11.
É isso. Espero que esteja certo. Caso tenha algum erro me informem.
Abraço a todos
On Oct 23, 12:53 pm, Sergio Alvarez <sergio1...@gmail.com> wrote:
> Dica 1: O que você ganha considerando os restos dos números da forma 11...1
> na divisão por n?
>
Cristiano Santos Benjamin
Oct 24, 2009, 3:26:37 AM10/24/09
to Matemática Radical
Só reescrevendo o penúltimo parágrafo corrigindo um erro de digitação
"Podemos também verificar facilmente se r_(i)=0 então r_(i+1)=r_(1),
"Podemos também verificar facilmente se r_(i)=0 então r_(i+1)=r_(1),
r_
(i+2)=r_(2), r_(i+3)=r_(3), ... E em particular r_(i)=r_(wi)=0 para
todo w pertencentes os naturais. Logo m possui infinitos múltiplos da
forma 111...11."
On Oct 24, 4:20 am, Cristiano Santos Benjamin
(i+2)=r_(2), r_(i+3)=r_(3), ... E em particular r_(i)=r_(wi)=0 para
todo w pertencentes os naturais. Logo m possui infinitos múltiplos da
forma 111...11."
Sergio Alvarez
Oct 24, 2009, 2:05:31 PM10/24/09
to matematic...@googlegroups.com
É isso aí, Cris! Muito bom! Eu abri o email pensando em passar a próxima dica e tive a agradável surpresa de encontrar a sua solução. De qualquer forma gostaria de dar algumas explicações.
1. Afinal, o que você ganha considerando os restos dos números da forma 11...1 na divisão por n?
Há apenas um número finito de restos na divisão por n: 0,1,...,n-1.
É interessante que mesmo sem saber exatamente que número é esse (o valor de n pode até estar fixo, mas não é um dado do problema), o simples fato de que há apenas um número finito de restos é uma informação muito relevante.
2. Como o fato de que há apenas um número finito de restos na divisão por n nos ajuda a resolver esse problema?
Você já ouviu falar no "Princípio da Casa dos Pombos"? Ele diz o seguinte:
"Se mais que nr pombos entram em apenas r casas de pombo, então alguma casa terá pelo menos r+1 pombos. "
É um fato simples de se demonstrar (tente!) e é muito útil! Agora, vamos responder a pergunta.
Há apenas um número finito de restos na divisão por n. Imagine que cada um deles corresponde a uma casa de pombo. (Por exemplo, imagine uma casa de pombo com o número 0, outra com o número 1... terminando na casa de número n-1). Cada número da forma 11...1 corresponde a um pombo. Então, temos infinitos pombos para apenas um número finito de casas.
Logo, pelo Princípio da Casa dos Pombos, há dois números da forma 11...1 que deixam o mesmo resto na divisão por n.
3. Legal, mas o que a gente queria não era encontrar um múltiplo de n da forma 11...1?
Ah, sim! Eu quase esqueci...
Há dois números da forma 11...1 que deixam o mesmo resto na divisão por n. Isso significa que a diferença entre eles é um múltiplo de n.
Digamos que um deles tenha i algarismos e o outro, j algarismos. Naturalmente, podemos supor i<j. Então, a diferença desses dois números é da forma 11..100...0 (um bloco de j-i 1's seguido de um bloco de i 0's). Podemos escrever esse número assim: 11...1*10^i.
Sabemos que n é um divisor de 11...1*10^i (bloco de j-i 1's). Mas, por hipótese, mdc(n,2) = mdc(n,5) = 1. Logo, mdc(n,10^i) = 1. Portanto, n é um divisor de 11...1.
Considerações finais:
1. Como o Cris observou, há infinitos números da forma 11...1 que deixam o mesmo resto na divisão por n. Podemos mostrar então que n possui infinitos múltiplos da forma 11...1. (Parecia estranho existir algum, e agora podemos ver que há infinitos!)
2. A nossa aplicação do Princípio da Casa dos Pombos exigiu apenas que houvesse mais pombos que casas de pombo. Então, poderíamos ter considerado apenas os números: 1, 11, 111, ..., 11...1 (bloco de n 1's) Dentre estes certamente há dois que deixam o mesmo resto na divisão por n. E aplicando o argumento acima concluímos que há um múltiplo de n da forma 11...1, com no máximo n-1 1's. Legal, né?
3. E agora, será que a gente consegue encontrar um múltiplo de 17 da forma 11...1? Com certeza existe um com no máximo 16 algarismos. Eu mesmo nem sei qual é e acho que uma calculadora não ajudaria muito nesse caso. Talvez um argumento usando congruências... quem sabe? Parece que temos um pequeno desafio.
1. Afinal, o que você ganha considerando os restos dos números da forma 11...1 na divisão por n?
Há apenas um número finito de restos na divisão por n: 0,1,...,n-1.
É interessante que mesmo sem saber exatamente que número é esse (o valor de n pode até estar fixo, mas não é um dado do problema), o simples fato de que há apenas um número finito de restos é uma informação muito relevante.
2. Como o fato de que há apenas um número finito de restos na divisão por n nos ajuda a resolver esse problema?
Você já ouviu falar no "Princípio da Casa dos Pombos"? Ele diz o seguinte:
"Se mais que nr pombos entram em apenas r casas de pombo, então alguma casa terá pelo menos r+1 pombos. "
É um fato simples de se demonstrar (tente!) e é muito útil! Agora, vamos responder a pergunta.
Há apenas um número finito de restos na divisão por n. Imagine que cada um deles corresponde a uma casa de pombo. (Por exemplo, imagine uma casa de pombo com o número 0, outra com o número 1... terminando na casa de número n-1). Cada número da forma 11...1 corresponde a um pombo. Então, temos infinitos pombos para apenas um número finito de casas.
Logo, pelo Princípio da Casa dos Pombos, há dois números da forma 11...1 que deixam o mesmo resto na divisão por n.
3. Legal, mas o que a gente queria não era encontrar um múltiplo de n da forma 11...1?
Ah, sim! Eu quase esqueci...
Há dois números da forma 11...1 que deixam o mesmo resto na divisão por n. Isso significa que a diferença entre eles é um múltiplo de n.
Digamos que um deles tenha i algarismos e o outro, j algarismos. Naturalmente, podemos supor i<j. Então, a diferença desses dois números é da forma 11..100...0 (um bloco de j-i 1's seguido de um bloco de i 0's). Podemos escrever esse número assim: 11...1*10^i.
Sabemos que n é um divisor de 11...1*10^i (bloco de j-i 1's). Mas, por hipótese, mdc(n,2) = mdc(n,5) = 1. Logo, mdc(n,10^i) = 1. Portanto, n é um divisor de 11...1.
Considerações finais:
1. Como o Cris observou, há infinitos números da forma 11...1 que deixam o mesmo resto na divisão por n. Podemos mostrar então que n possui infinitos múltiplos da forma 11...1. (Parecia estranho existir algum, e agora podemos ver que há infinitos!)
2. A nossa aplicação do Princípio da Casa dos Pombos exigiu apenas que houvesse mais pombos que casas de pombo. Então, poderíamos ter considerado apenas os números: 1, 11, 111, ..., 11...1 (bloco de n 1's) Dentre estes certamente há dois que deixam o mesmo resto na divisão por n. E aplicando o argumento acima concluímos que há um múltiplo de n da forma 11...1, com no máximo n-1 1's. Legal, né?
3. E agora, será que a gente consegue encontrar um múltiplo de 17 da forma 11...1? Com certeza existe um com no máximo 16 algarismos. Eu mesmo nem sei qual é e acho que uma calculadora não ajudaria muito nesse caso. Talvez um argumento usando congruências... quem sabe? Parece que temos um pequeno desafio.
2009/10/24 Cristiano Santos Benjamin <csbenja...@hotmail.com>
Sergio Alvarez
Oct 28, 2009, 12:55:42 AM10/28/09
to matematic...@googlegroups.com
Finalmente, vamos encontrar um múltiplo de 17 da forma 11...1.
A princípio, poderíamos aplicar a idéia da solução proposta para o problema, que mostra a existência de um múltiplo dessa forma através do Princípio da Casa dos Pombos. Mas isso não seria nem um pouco prático. (Experimenta!)
Vamos tentar algo mais elegante...
11...1 = (10^n - 1)/9,
onde n é o número de dígitos 1 no membro esquerdo.
Então, 9 * 11...1 = 10^n - 1.
Como mdc(17,9) = 1, 17 é divisor de 11...1 se, e só se, é divisor de 9 * 11...1.
Ou seja, 17 divide 11...1 se, e só se, 17 divide 10^n-1.
Portanto, 17 divide 11...1 se, e só se, 10^n = 1 mod 17.
Qual é o menor valor de n para o qual isso acontece?
Pelo Pequeno Teorema de Fermat, 10^16 = 1 mod 17.
Por outro lado,
10 = -7 mod 17, 10^2 = -2 mod 17, 10^4=4 mod 17, 10^8=-1 mod 17
Logo, n=16 é o menor valor de n para o qual 10^n = 1 mod 17
Resulta que 11...1 (16 dígitos iguais a 1) é o menor múltiplo de 17 com dígitos todos iguais a 1.
Agora, a gente já sabe com quantos 1's se faz um múltiplo de 17.
A princípio, poderíamos aplicar a idéia da solução proposta para o problema, que mostra a existência de um múltiplo dessa forma através do Princípio da Casa dos Pombos. Mas isso não seria nem um pouco prático. (Experimenta!)
Vamos tentar algo mais elegante...
11...1 = (10^n - 1)/9,
onde n é o número de dígitos 1 no membro esquerdo.
Então, 9 * 11...1 = 10^n - 1.
Como mdc(17,9) = 1, 17 é divisor de 11...1 se, e só se, é divisor de 9 * 11...1.
Ou seja, 17 divide 11...1 se, e só se, 17 divide 10^n-1.
Portanto, 17 divide 11...1 se, e só se, 10^n = 1 mod 17.
Qual é o menor valor de n para o qual isso acontece?
Pelo Pequeno Teorema de Fermat, 10^16 = 1 mod 17.
Por outro lado,
10 = -7 mod 17, 10^2 = -2 mod 17, 10^4=4 mod 17, 10^8=-1 mod 17
Logo, n=16 é o menor valor de n para o qual 10^n = 1 mod 17
Resulta que 11...1 (16 dígitos iguais a 1) é o menor múltiplo de 17 com dígitos todos iguais a 1.
Agora, a gente já sabe com quantos 1's se faz um múltiplo de 17.
2009/10/24 Sergio Alvarez <sergi...@gmail.com>
Reply all
Reply to author
Forward
0 new messages