Congruências e divisibilidade — Um Problema da Purdue University [Republicação] :: Congruences and Divisibility — A Purdue University Problem [Repost]

(Original)

pdf: ver caderno

Versão portuguesa da entrada “Congruences and Divisibility– A Purdue University Problem“

Tradução do enunciado do Problema original [PROBLEM OF THE WEEK, Problem No. 12 (Spring 2009 Series)]:

« Para quantos inteiros positivos é que  não é divisível por ?

Justifique a sua resposta sem utilizar o computador. »

“For how many positive integers is not divisible by ?

Justify your answer without the use of computers.”

Eis a tradução da  minha resolução (aceite):

Se , então . Esta propriedade aplicada a dá em geral, para 

o que significa que os restos da divisão de  por formam uma sucessão periódica de comprimento com início em

Quanto a , dado que: a) se e , então e b) se , então , temos em geral, para

o que quer dizer que os restos da divisão de por 7 formam uma sucessão  periódica  de comprimento 7 que começa em

Se  e , então . Seja Em consequência de (1) e (2) obtemos

Os restos da divisão de  por formam outra sucessão periódica de comprimento que se inicia também em . Apresentamos abaixo quatro exemplos da determinação destes restos.

Para os seguintes termos não são divisíveis por :

.

Assim para , há  termos que não são divisíveis por .

Dos restantes 4 termos e   não são divisíveis por , o que dá um total de números não divisíveis por .

Quatro exemplos do cálculo dos restos:

()

()

()

()

• * * *

PROBLEM OF THE WEEK, Problem No. 12 (Spring 2009 Series):

“ Problem. For how many positive integers is not divisible by ?

Justify your answer without the use of computers. ”

Here is my solution (accepted).

If , then . Applied to this property gives in general for

which means that the remainders of the division of by form a periodic sequence of length starting at

As for since (a) if and , then and (b) if , then , we have in general for

which means that the remainders of the division of by 7 form a periodic sequence of length 7 starting at

If and , then . Let Therefore from (1) and (2) we have

The remainders of the division of by form another periodic sequence of length which starts also at . Four examples of the evaluation of these remainders are presented below.

For the following terms are not divisible by :

.

Hence for , there are  terms that are not divisible by .

From the remaining 4 terms and   are not divisible by , which gives a total of numbers not divisible by .

Four examples of the evaluation of the remainders:

()

()

()

()

 

Editado em 12-03-2019 para acrescentar a versão original inglesa