Let $p > 10^9$ be a prime number such that $4p + 1$ is also prime. Prove that the decimal expansion of $\frac{1}{4p+1}$ contains all the digits $0,1, \ldots, 9$.
Problem
Source: Croatia TST 2016
Tags: number theory, prime numbers, prime, primitive root, decimal representation
02.05.2016 19:01
This problem is originally proposed in Bulgarian Team Selection Test-2015 , By Nikolai Beluhov , i remembered a solution by use of Primitive roots and 4-power residues modulo $p$
10.05.2016 09:39
Here's a sketch: Let $4p+1 = q$ then if we let the order of $10$ mod $q$ be $d$, then the decimal expansion of $\frac{1}{q}$ is a repeating decimal of $d$ digits. Now $d$ must divide $4p$ and since $d$ can't be $0,1,2$ or $4$ as $q > 10^9$, it must be either $p,2p$ or $4p$. We will deal with the case where $d = p$. The other cases are similar. The key fact is to note that if for some natural $c$, if $10^k \equiv c \pmod q$ for some $k$, then the repeating part of the decimal expansion of $\frac{c}{q}$ is simply a permutation of the repeating part of the expansion of $\frac{1}{q}$. To see why, just perform the long division procedure and note that you are just starting at the $k^{th}$ zero instead. Now let $X$ be the repeating decimal. Then we have that $cX$ share the same digits for $p$ different $c$'s where $1 \leq c \leq 4p$. Call those $c$ "good". Let $X$ have $m$ digits and for each $cX$, split it into $\overline{AB}$ where $B$ has $m$ digits and $A$ are the remaining leading digits. Now if the decimal expansion does not contain some digit say $9$, then $A$ will not contain $9$ either for all our good $c$'s. Combined with the fact that at least $\frac{1}{4}$ of our $c$'s are good and that $p > 10^9$, some calculations will show that this is not possible as there are too many $A$'s that are paired up with the non-good $c$'s.
01.11.2016 13:04
fattypiggy123 wrote: Here's a sketch: Let $4p+1 = q$ then if we let the order of $10$ mod $q$ be $d$, then the decimal expansion of $\frac{1}{q}$ is a repeating decimal of $d$ digits. Now $d$ must divide $4p$ and since $d$ can't be $0,1,2$ or $4$ as $q > 10^9$, it must be either $p,2p$ or $4p$. We will deal with the case where $d = p$. The other cases are similar. The key fact is to note that if for some natural $c$, if $10^k \equiv c \pmod q$ for some $k$, then the repeating part of the decimal expansion of $\frac{c}{q}$ is simply a permutation of the repeating part of the expansion of $\frac{1}{q}$. To see why, just perform the long division procedure and note that you are just starting at the $k^{th}$ zero instead. Now let $X$ be the repeating decimal. Then we have that $cX$ share the same digits for $p$ different $c$'s where $1 \leq c \leq 4p$. Call those $c$ "good". Let $X$ have $m$ digits and for each $cX$, split it into $\overline{AB}$ where $B$ has $m$ digits and $A$ are the remaining leading digits. Now if the decimal expansion does not contain some digit say $9$, then $A$ will not contain $9$ either for all our good $c$'s. Combined with the fact that at least $\frac{1}{4}$ of our $c$'s are good and that $p > 10^9$, some calculations will show that this is not possible as there are too many $A$'s that are paired up with the non-good $c$'s. I feel some difficulty to understand your post. First of all, at my opinion, if $X$ is the repeating decimal, then $cX$ can be written $\overline{AB}$ where $B$ has $m$ digits and $A$ are the remaining leading digits. Then at my opinion, we should conclude that $A+B$ has the same digit with $X$, not $B$.
26.03.2017 10:30
danepale wrote: Let $p > 10^9$ be a prime number such that $4p + 1$ is also prime. Prove that the decimal expansion of $\frac{1}{4p+1}$ contains all the digits $0,1, \ldots, 9$. can u give your solution pls
29.05.2017 21:41
Note that $10^{4p}\equiv 1$ mod $4p+1$ implies that the order of $10$ modulo $4p+1$ is either $1,2,4,p,2p,4p$. Since $p>10^9$, it's clear that the order is restricted to $\{p,2p,4p\}$. Let $S$ be the reduced set of residues of the form $10^k$ modulo $4p+1$. Note that for any $s\in S$, $\dfrac{s}{4p+1}$ and $\dfrac{1}{4p+1}$ have the same repeating block in their decimal expansions, since they are just shifts by some $10^k$. If $10$ has order $4p,2p$, or $p$ respectively, then $10$ can be written in the form $g, g^2, g^4$, respectively, for some primitive root $g$. In all cases, $\{10^k\}$ will cover all residues of the form $g^{4k}$ modulo $4p+1$, so every quartic residue is an element of $S$. Now consider all the perfect 4th powers $1^4,2^4,...$ which are at most $4p+1$. I claim that for each $d\in \{0,1,2,...9\}$, there exists some $k$ such that $\dfrac{d}{10} \le \dfrac{k^4}{4p+1} < \dfrac{d+1}{10}$; this will imply the first digit of $\dfrac{k^4}{4p+1}$ is $d$, and since $\dfrac{k^4}{4p+1}, \dfrac{1}{4p+1}$ are cyclic shifts of each other, we will be able to conclude that $\dfrac{1}{4p+1}$ contains every digit $d$ somewhere in its decimal expansion.
.