pdf: ver caderno
Versão portuguesa aqui
“ 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:
Remark: typos corrected. [In the 2nd. last paragraph before the examples: “there are” added]
Edited: May 29, 2009: Portuguese version removed and posted here