Denote by S the set of all primes such the decimal representation of $\frac{1}{p}$ has the fundamental period divisible by 3. For every $p \in S$ such that $\frac{1}{p}$ has the fundamental period $3r$ one may write
\[\frac{1}{p}=0,a_{1}a_{2}\ldots a_{3r}a_{1}a_{2} \ldots a_{3r} \ldots , \]
where $r=r(p)$; for every $p \in S$ and every integer $k \geq 1$ define $f(k,p)$ by \[ f(k,p)= a_{k}+a_{k+r(p)}+a_{k+2.r(p)}\]
a) Prove that $S$ is infinite.
b) Find the highest value of $f(k,p)$ for $k \geq 1$ and $p \in S$
Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions
The fundamental period of $\frac{1}{p}$ is clearly the order of 10 modulo $p$. For any positive integer $r$, $10^{2r} + 10^r + 1$ is clearly not a power of 3 (or else $10^{3r} - 1$ would be a power of 3, which is clearly not possible.) Hence, for any positive integer $r$, we can pick $p$ to be any prime divisor distinct from 3 of $10^{2r} + 10^r + 1$. Then $p | 10^{3r} - 1 = (10^r - 1)(10^{2r} + 10^r + 1)$, and $p \not | 10^r - 1$ (or else $0 \equiv 10^{2r} + 10^r + 1 \equiv 3 \pmod p$, i.e., $p=3$.) Hence, the order of $10$ modulo $p$ is $3r$. Since $3r | p - 1$, we can find arbitrarily large (and hence infinitely many) $p$ for which the order of 10 modulo $p$ is $3r$ by picking sufficiently large $r$.
For part b, I claim that the answer is 19. $\frac{1}{7} = 0.\overline{142857}$, so $19 = f(2,7)$ is attainble. We will now show that nothing greater than 19 can be attained.
We may assume that $p \neq 2,5$. We note that the $k$th, $k+r$th, and $k+2r$th digit past the decimal point are the rightmost digits of $\lfloor \frac{10^k}{p} \rfloor$, $\lfloor \frac{10^{k+r}}{p} \rfloor$, and $\lfloor \frac{10^{2k+r}}{p} \rfloor$, respectively. Let $10^k \equiv a_0 \pmod p$, $10^{k+r} \equiv a_1 \pmod p$, and $10^{k+2r} \equiv a_2 \pmod p$, where $0 < a_0, a_1, a_2 < p$. Then the $k$th, $k+r$th, and $k+2r$th digit past the decimal point are just the rightmost digits of $\frac{10^k - a_0}{p}$, $\frac{10^{k+r} - a_1}{p}$, and $\frac{10^{k+2r} - a_2}{p}$, respectively. Since $\frac{10^k - a_0}{p}$, $\frac{10^{k+r} - a_1}{p}$, and $\frac{10{k+2r} - a_2}{p}$ are all integers, their sum $\frac{10^k(10^{2r} + 10^r + 1}}{p} - \frac{a_0 + a_1 + a_2}{p}$ is an integer as well. Since $3r$ is the order of 10 mod $p$, $p \not | 10^r - 1$; since $p | 10^{3r} - 1 = (10^r - 1)(10^{2r} + 10^r + 1)$, $\frac{10^2r + 10^r + 1}{p}$ is an integer. It follows that $p | a_0 + a_1 + a_2$, that is, $a_0 + a_1 + a_2 = p$ or $a_0 + a_1 + a_2 = 2p$.
The rightmost digits of $\frac{10^k - a_0}{p}$, $\frac{10^{k+r} - a_1}{p}$, and $\frac{10{k+2r} - a_2}{p}$, are $b_0 \equiv -a_0 p^{-1} \pmod{10}$, $b_1 \equiv -a_1 p^{-1} \pmod{10}$, and $b_2 \equiv -a_2 p^{-1} \pmod{10}$, where $0 \leq b_0, b_1, b_2 < 10$. Since $a_2 = p - a_0 - a_1$ or $2p - a_0 - a_1$, $b_2$ must always be equal to $9 - (b_0 + b_1)$, $8 - (b_0 + b_1)$, $19 - (b_0 + b_1)$, or $18 - (b_0 + b_1)$ (depending on whether $0 < 8,9,18,19 - (b_0 + b_1) < 10$ and whether $a_2 = p - a_0 - a_1$ or $a_2 = 2p - a_0 - a_1$.) In each case, we have that $b_0 + b_1 + b_2 \leq 19$, which completes our proof.
Zhero wrote:
Hence, for any positive integer $r$, we can pick $p$ to be any prime divisor distinct from 3 of $10^{2r} + 10^r + 1$. Then $p | 10^{3r} - 1 = (10^r - 1)(10^{2r} + 10^r + 1)$, and $p \not | 10^r - 1$ (or else $0 \equiv 10^{2r} + 10^r + 1 \equiv 3 \pmod p$, i.e., $p=3$.) Hence, the order of $10$ modulo $p$ is $3r$. Since $3r | p - 1$, we can find arbitrarily large (and hence infinitely many) $p$ for which the order of 10 modulo $p$ is $3r$ by picking sufficiently large $r$.
I think this argument only guarantees that the order of $10$ modulo $p$ is a multiple of $3$, since, for example, $37|10^4+10^2+1$ while the order of $10$ modulo $37$ is really $3$, not $6$. A simple way to fix this is to let $r$ be prime and $p$ not divide $10^3-1=999$, so the only possible orders are $1,3,r,3r$, the first three of which are impossible.
Edit: I also have a different way for (b). Note that
\[\frac{10^{3r}-1}{p}=\sum_{i=0}^{r-1}10^i(a_{3r-i}+10^ra_{2r-i}+10^{2r}a_{r-i}).\]Since $p$ does not divide $10^r-1$, we can take this modulo $10^r-1$ to get
\[0 \equiv \sum_{i=0}^{r-1}10^if(r-i,p) \pmod{10^r-1}.\]But
\[0 \le \sum_{i=0}^{r-1}10^if(r-i,p) \le 27\sum_{i=0}^{r-1}10^i = 3(10^r-1),\]with equality only when $10^{3r}-1=0$ or $p=1$. So equality cannot occur, and
\[\sum_{i=0}^{r-1}10^if(r-i,p) \in \{10^r-1, 2\cdot10^r-2\}.\]We can prove that if
\[\sum_{i=0}^{r-1}10^if(r-i,p) \in \{-1, -2\} \pmod{10^r},\]then $f(r-i,p)$ is either $-1$ or $-2$ modulo $10$ for all $i$ by induction on $r$. For $r=1$ this is obvious. Now for arbitrary $r\ge2$, we consider the two cases separately. If
\[\sum_{i=0}^{r-1}10^if(r-i,p) \equiv -1 \pmod{10^r},\]then taking modulo $10$ tells us $f(r,p)\equiv-1\pmod{10}$, so it is either $9$ or $19$. Both of these cases give
\[\sum_{i=0}^{r-2}10^if((r-1)-i,p) \in \{-1, -2\} \pmod{10^{r-1}},\]so the result follows by the inductive hypothesis here. Now if
\[\sum_{i=0}^{r-1}10^if(r-i,p) \equiv -2 \pmod{10^r},\]then taking modulo $10$ tells us $f(r,p)\equiv-2\pmod{10}$, so it is either $8$ or $18$. Both of these cases give
\[\sum_{i=0}^{r-2}10^if((r-1)-i,p) \in \{-1, -2\} \pmod{10^{r-1}},\]so again we are done by the inductive hypothesis. As Zhero already showed, $f(2,7)=19$, so we're done.
Here's a different way for part a):
By Zsigmondy's theorem, $10^{3r}-1$ has at least one primitive prime factor for each value of integer $r > 0$, so we are done, because clearly $ord_{10}(p) = 3r$.
Here's a slicker way for part a):
Suppose only finitely many primes $p_1, p_2, p_3, \dots, p_k$ are in $S$. Consider a prime factor $p$ of $10^{2P} + 10^P + 1$, where $P = (p_1 - 1)(p_2 - 1) \dots (p_k - 1)$. Since clearly $2, 3, 5$ are not in $S$, Fermat gives us $P \equiv 3 \pmod p$, so $p$ is in and not in $S$, contradiction. Thus $S$ is infinite.
For part a), take $p\mid \Phi_{3m} (10)$ for any $m>0$.
For part b), note that $p=7,k=2$ gives $f(k,p)=19$. I claim this is the answer. Let $l=r(p)$ for convenience. Note that $a_k$ is just the last digit of $\left\lfloor \dfrac{10^k}{p}\right\rfloor$. If $a$ is the residue of $10^k$ modulo $10p$, it follows that $a_k = \left\lfloor \dfrac{a}{p}\right\rfloor$. Similarly define $b,c$ to be the residues of $10^{k+l}, 10^{k+2l}\pmod {10p}$.
Note that $f(k,p) = \left\lfloor \dfrac{a}{p}\right\rfloor + \left\lfloor \dfrac{b}{p}\right\rfloor +\left\lfloor \dfrac{c}{p}\right\rfloor \le \dfrac{a+b+c}{p}$, which is an integer as $p\mid 10^{2l}+10^l+1$ and a multiple of $10$ as $10\mid a,b,c$. Since $a,b,c<10p$ this implies this last quantity is $\le 20$. For equality to hold we need $p\mid a,b,c$, but since $10\mid a,b,c$ this implies $a=b=c=0$, contradiction. Hence $20$ is unattainable so $19$ is the maximum.
The fundamental period of $\frac{1}{p}$ is $ord_p(10)$.
a) We need to prove that there are infinitely many primes $p$ such that $3|ord_p(10)$.By, Zsigmondy's theorem, for any $r\ge 2$, $10^{3r}-1$ has a prime divisior $p$ which does not devide any $10^n-1$ for $n=1,2,...,3r-1$.So for this prime $p$ we have $ord_p(10)=3r$.$\blacksquare$
(b)For a prime $p$ in $S$ as $ord_p(10)=3r$ so $p|10^{2r}+10^r+1$,since $p$ can't devide $10^r-1$.
Now write
\[\frac{1}{p}=0,a_{1}a_{2}\ldots a_{3r}a_{1}a_{2} \ldots a_{3r} \ldots , \]Observe that
$\frac{10^{j-1}}{p}=a_1a_2\ldots a_{j-1}.a_{j}a_{j+1}\ldots$
Write $x_j=\frac{10^{j-1}}{p}$ and $y_j=\{x_j\}=0.a_{j}a_{j+1}\ldots $.So $a_j<10y_j$.
Hence,
$f(k,p)=a_{k}+a_{k+r(p)}+a_{k+2.r(p)}<10(y_{k}+y_{k+r(p)}+y_{k+2.r(p)}$
Now as $x_{k}+x_{k+r(p)}+x_{k+2.r(p)}=\frac{(10^{k-1})(1+10^r+10^{2r})}{p}$ is a integer so $y_{k}+y_{k+r(p)}+y_{k+2.r(p)}=\{x_{k}\}+\{x_{k+r(p)}\}+\{x_{k+2.r(p)}\}\le 2$.
So
$f(k,p)=a_{k}+a_{k+r(p)}+a_{k+2.r(p)}<2*10=20$
Now for $\frac{1}{7}$ it is easy to check that $19$ can be achieved.$\blacksquare$
By Zsigmondy's, for each $r$ there exists a prime $p_r$ dividing $10^{3r}-1$ but not $10^k-1$ for any $k<r$. Thus, the fundamental period of $\tfrac 1 {p_r}$ is $3r$. Clearly, $p_1,p_2,p_3,\dots$ are all distinct, so $S$ is infinite.
$~$
To find the maximum of $f(k,p)$, we note that
\[\frac{10^{3r}-1}{p}=\overline{a_1a_2\dots a_{3r-1}}=\sum_{i=1}^{3r}{10^{3r-i}a_{i}}\]Note that $10^r-1$ divides that expression. Therefore,
\begin{align*}
10^r-1 &\mid \sum_{i=1}^{3r}{10^{3r-i}a_{i}} \\
10^r-1 &\mid \sum_{i=1}^{r}{10^{3r-i}a_i+10^{2r-i}a_{i+r}+10^{r-i}a_{i+2r}} \\
10^r-1 &\mid \sum_{i=1}^{r}{10^{r-i}a_i+10^{r-i}a_{i+r}+10^{r-i}a_{i+2r}} \\
10^r-1 &\mid \sum_{i=1}^{r}{10^{r-i}f(i,p)}
\end{align*}However, note that
\[\sum_{i=1}^{r}{10^{r-i}f(i,p)} \le \sum_{i=1}^{r}{10^{r-i}\cdot 27}=27\sum_{i=1}^{r}{10^{i}}=3(10^r-1)\]where equality cannot occur because that requires all digits to be nine, violating the fundamental period being divisible by $3$. Therefore, the value is either $2(10^r-1)$ or $10^r-1$. In particular, they are equivalent to $-1$ or $-2\pmod {10^r}$.
$~$
Define the sequence $\{x\}$ for $1,2,\dots,r$ according to the constraint
\[x_k=\sum_{i=k}^{r}{10^{r-i}f(i-k,p)}\]Other than the closed form formula, we also have recursion $x_k=\tfrac{x_{k-1}-f(r-k+1,p)}{10}$ for $k=2,3,\dots,r$. Note that inductively we can show $x_{k-1}\equiv 98$ or $99\pmod {100}$ and so $f(r-k+1,p)\equiv 8$ or $9\pmod {10}$. We also have $f(r,p)\equiv 8$ or $9\pmod {10}$ which is obvious. Thus, $f(r,p)\le 19$ which can be achieved at $f(2,7)$.
