UM POUCO DA OBMEP

Eudes Antonio Costa
Fernando Soares Carvalho

As questões a seguir foram propostas a alunos do PIC – Programa de Iniciação Científica da OBMEP – Olimpíada Brasileira de Matemática das Escolas Públicas, no ano 2014, e nos motivaram a pesquisar sobre os números repunits (repetição da unidade). Este texto pretende partilhar parte de nossa experiência.

AS QUESTÕES

Questão1 (Banco de Questões/OBMEP 2008)

Roberto quer escrever o número R₆ = 111111 como um produto de dois números, nenhum deles terminado em 1. Isso é possível? Por quê?

Como a soma dos algarismos de 111111 é 6, pelo critério de divisibilidade por 3, temos que 111111 é divisível por 3, logo uma resposta imediata é

111111 = 3 × 37037.

Perguntamos aos alunos se existiriam produtos diferentes desse, sem o algarismo 1. Vejamos a solução dessa questão, que chamaremos questão 1'.

Resolução da questão 1'

Temos R₆ = (10⁵ + 10⁴) + (10³ + 10²) + (10¹ + 10⁰).

Observemos o seguinte resultado:

Resultado 1: Se n é um número natural maior do que 1, então 10^{n – 1} + 10 ⁿ é um múltiplo de 11.

Para verificar o resultado, basta escrever

10^{n – 1} + 10 ⁿ = 10^{n – 1}(1 + 10) = 10^{n – 1 × 11.}

Esse Resultado 1 garante que R₆ é soma de múltiplos de 11, logo é um múltiplo de 11.

Já observamos que R₆ = 111111 = 3 × 37037 e, por ser múltiplo de 11, ainda podemos escrever 111111 = 3 × 11 × 3367; dividindo 3367 por 7 e depois 481 por 13, obtemos:

R₆ = 111111 = 3 × 7 × 11 × 13 × 37.

Escrevendo todas as possibilidades de produtos e evitando os que apresentam o algarismo 1, obtemos:

3 × 37037; 7 × 15873; 13 × 8547; 37 × 3003;

33 × 3367; 39 × 2849; 77 × 1443;

259 × 429; 143 × 777; 407 × 273.

Logo, Roberto tem 10 opções para escrever R₆ como deseja.

Essa Questão 1 motivou a Questão 2, a seguir, que foi proposta no fórum (inserido no Portal do PIC) de discussão online que é utilizado pelos alunos do PIC para estudos complementares.

Questão 2 (proposta no Portal do PIC)

Seja R_k um número natural formado (na base 10) por k algarismos todos iguais a 1, para algum k ∈ ℕ^*, ou seja, . Por exemplo, R₁ = 1,

R₂ = 11, R₃ = 111 e sucessivamente.

a) Qual é o resto da divisão de R₂₀₁₄ por 7?

b) Existem números R_k, k ≥ 2, que são divisores de R₂014 ?

Resolução do item a) da questão 2

A maioria dos nossos alunos resolveu corretamente o item a) da questão 2, e as soluções apresentadas por eles eram similares à seguinte:

Temos:

R₁ =1 = 0 × 7 + 1

R₂ =11 = 1 × 7 + 4

R₃ =111 = 15 × 7 + 6

R₄ =1111 = 158 × 7 + 5

R₅ =11111 = 1587 × 7 + 2

R₆ =111111 = 15873 × 7 + 0

R₇ = 1111111 = 158730 × 7 + 1

R₈ = 11111111 = 1587301 × 7 + 4

R₉ = 111111111 = 15873015 × 7 + 6

R₁₀= 1111111111 = 158730158 × 7 + 5

...

Assim, os restos das divisões de R₁, R₂, R₃, R₄, R₅, ... por 7 são respectivamente 1, 4, 6, 5, 2, 0, e isso se repete em ciclos de tamanho 6.

Como 2014 = 6 × 335 + 4, ou seja, o resto da divisão de 2014 por 6 é 4, observando o padrão da repetição dos restos, concluímos que o resto da divisão de R₂₀₁₄ por 7 é 5.

Quanto à resolução do item b) da questão 2, não obtivemos grande sucesso por parte dos alunos. Poucos foram os que perceberam que R₂ = 11 é um divisor de R₂₀₁₄. Sugerimos aos alunos que investigassem se R₂ e R₃ eram divisores de R₆ e se esse fato poderia ser generalizado para outros R_k e seus divisores.

Antes de mostrar uma solução desse item b) da questão 2, vamos apresentar o estudo que fizemos dos R_k, alguns exemplos e afirmações.

NÚMEROS R_k E SEUS FATORES

Números da forma R_k são chamados repunits (repetição de unidade). O termo repunit foi utilizado pela primeira vez por Beiler [3], que apresentou a fatoração de R_k para alguns valores de k.

A seguir, reproduzimos uma TABELA com fatorações de R_k para 2 ≤ k ≤ 19 e k = 53.

Existe uma dificuldade computacional para verificar se R_k é um número composto ou não (imagine R_k com milhões de algarismos), apontado em diversos trabalhos, por exemplo, [1], [2] e [5]. Os valores de k para os quais sabemos que R_k é primo são k = 2, 19, 23, 317 e 1031. Sabe-se também que, se k = 49081, 86453, 109297 ou 270343, então R_k passa por diversos testes probabilísticos de primalidade, ou seja, é um provável número primo. Em 2012 foram testados todos os valores de R_k para k < 2.500.000, mas nenhum novo provável primo foi encontrado. Uma questão, ainda em aberto, é se existem infinitos números primos da forma R_k.

ALGUNS EXEMPLOS E AFIRMAÇÕES

Observando a tabela anterior, apresentaremos alguns exemplos e faremos algumas afirmações sobre os números repunits R_k .

Exemplo 1

Observemos que R₃ = 111 = 3 × 37, R₆ = 111111 = 3 × 37037 e R₉ = 111111111 = 3 × 37037037. Isso leva, pelo critério de divisibilidade por 3, à:

Afirmação 1

Para todo k ∈ ℕ*, R_k é um número múltiplo de 3 se e somente se k também o é.

Exemplo 2

Observamos ainda que

R₄ = 1111 = 11 × 101,

R₆ = 111111 = 11 × 10101 e

R₈ = 11111111 = 11 × 1010101.

Isso sugere:

Afirmação 2

Para todo k ∈ ℕ*, se k é um número par (múltiplo de 2), então R_k é múltiplo de 11.

A verificação dessa Afirmação 2 é feita usando o Resultado 1, demonstrado anteriormente. Vejamos:

é uma soma com k parcelas, logo com um número par de parcelas. Então podemos agrupar as parcelas aos pares:

10^k-1 + 10^k-2 +...+ 10³ + 10² + 10 + 1 =

(10^k-1 + 10^k-2) +...+( 10³ + 10²⁾ +( 10 + 1).

Pelo Resultado 1, cada soma dos pares entre parênteses é um múltiplo de 11, logo a soma toda, ou R_k, é um múltiplo de 11.

Exemplo 3

Observamos também que

R₆ = 111111 = 7 × 13 × 1221 e

R₁2 = 111111111111 = 7 × 13 × 1221001221

o que, junto com as afirmações 1 e 2, sugere:

Afirmação 3

Para todo k ∈ ℕ*, se k é um número múltiplo de 6, então R_k é múltiplo de 3, 7, 11 e 13.

Para verificar a Afirmação 3, só falta mostrar que R_k é um múltiplo de 7 e de 13, pois, pelas Afirmações 1 e 2, temos que R_k é múltiplo de 3 e de 11.

Para isso, observemos que, se n é um número natural, n ≥ 6, então

10^{n– 1} + 10^{n– 2} + 10^{n– 3} + 10^{n– 4} + 10^{n– 5} + 10^{n– 6} =

(10^{n– 1}+10^{n– 4})+(10^{n– 2}+10^{n– 5})+(10^{n– 3}+10^{n– 6}) =

10^{n– 4} (10³ + 1) + 10^{n– 5} (10³ + 1) + 10^{n– 6}(10³ + 1) =

1001(10^{n– 4} + 10^{n– 5} + 10^{n– 6}).

.E, como 1001 = 7 × 11 × 13, temos que uma soma de 6 parcelas de potências de 10, com expoentes consecutivos, é um múltiplo de 7 e de 13.

Ora, se k é um múltiplo de 6, então R_k é soma de grupos de potências de 10 como a anterior, logo é um múltiplo de 7 e de 13.

Exemplo 4

Considere

R₆ = 111111 = 10⁵ + 10⁴ + 10³ + 10² + 10¹ + 1 =

10⁴(10¹ + 1) + 10²(10¹ + 1) + (10¹ + 1) =

(10⁴ + 10² + 1)(10¹ + 1) = 10¹01 × 11 = 10¹01 × R₂.

R₆ = 111111 = 10⁵ + 10⁴ + 10³ + 10² + 10¹ + 1 =

10³(10² + 10¹ + 1) + (10²+ 10¹ + 1) =

(10³ + 1) (10² + 10¹ + 1) = 1001 × 111 = 1001 × R₃.

Ou seja,

R₆ = 10101 × R₂ = 1001 × R₃.

Exemplo 5

R₈ = 11111111 =

10⁷ + 10⁶+ 10⁵ + 10⁴ + 10³ + 10² + 10¹ + 1 =

10⁶(10¹ + 1) + 10⁴(10¹ + 1) + 10²(10¹ + 1) + (10¹ + 1) =

(10⁶ + 10⁴ + 10² + 1) × 11 =

1010101 × R₂.

Ou, ainda,

R₈ = 11111111 =

10⁴ (10³+ 10² + 10 + 1) + (10³ + 10² + 101 + 1) =

(10⁴ + 1) (10³ + 10² + 101 + 1) = 10001 × R₄.

Logo,

R₈ = 1010101 × R₂ = 10001 × R₄.

Exemplo 6

R₉ = 111111111= 1001001 × R₃, pois

R₉ = 108 + 106 + 105 + 10⁴ + 10³ + 10² + 10¹ + 1 =

106(10² + 101 + 1) + 10³(10² + 101 + 1) + + (10² + 101 + 1) = (106 + 10³ + 1)(10² + 101 + 1).

Esses exemplos sugerem:

Afirmação 4

Para quaisquer a, k ∈ ℕ*, se a divide k, então R_a divide R_k.

Para verificar essa afirmação, basta fazer:

Se a é um divisor de k, então k = ab, b um número natural, e R_k = R_ab.

R_ab =

10^{ab – 1} + 10^{ab – 2} +... + 10^a + 10^{a – 1} + ... + 10¹ + 1 =

(10^{a(b – 1)} + 10^{a(b – 2)} + ... + 1)(10^{a – 1} + 10^{a – 2}+ ... + 10² + 10¹ + 1) = (10^{a(b – 1)} + 10^{a(b – 2)} + ... + 1) × R_a.

Resolução do item b) da questão 2

Temos 2014 = 2 × 19 × 53 e então segue da Afirmação 4 que R₂, R19 e R₅₃ são divisores do tipo repunits de R₂₀₁₄.

CONSIDERAÇÕES

É claro que não esperávamos que nossos alunos do PIC percebessem que R₁₉ e R₅₃ são divisores repunits de R₂₀₁₄; esperávamos, contudo, que observassem que R₂ é divisor de qualquer R_k com k par. Também esperávamos que concluíssem que R₃ não é um divisor de R₂₀₁₄ , pois 3 é um divisor de R₃ e 3 não é um divisor de R₂₀₁₄, já que a soma de seus algarismos é 2014, que não é divisível por 3.

Também foi possível observar que, embora a Afirmação 4 implique ser necessário que k seja primo para R_k ser primo, essa condição não é suficiente, visto que (ver TABELA):

R₃ = 111 = 3 × 37, R₅ = 11111 = 41 × 271 e

R₇ = 239 × 4649 são compostos.

Para finalizar, propomos aos leitores as questões:

Questão 3

a) Quais números do tipo R_k são divisores de R₂₀₁₅?

b) Liste alguns divisores de R₂₀₁₅ que não são do tipo R_k.

Questão 4

Mostre que R_k é divisível por 91 se e somente se k é divisível por 6.

REFERÊNCIAS BIBLIOGRÁFICAS

[1] ANDREESCU, T. & GELCA, R. Mathematical Olympiad Challenges. New York, Birkhauser – Boston/ Springer-Verlag, 2000.

[2] BAXTER, L. R86453 is a New Probable Prime Repunit. 2000. <http://listserv.nodak.edu/scripts/wa.exe?A2=ind0010L=nmbrthryP=2557>.

[3] BEILER, A. H. 11111 ... 111. Ch. 11 in Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. New York, Dover, 1966.

[4] DUBNER, H. “Repunit R49081 is a Probable Prime”. Math. Comput. vol. 71, p. 833-835, 2002.

[5] MAVLO, D. “Absolute Prime Numbers”. The Mathematical Gazette. vol. 485, p. 299 – 304, 1995.

[6] WILLIAMS, H. C. & DUBNER, H. A. “Primality de R1031”. Math. of Computation. vol. 47, p. 703-711, 1986.