4
$\begingroup$

Let $P(n)$ be the period of the decimal expansion of $\frac{1}{n}$, i.e., $P(7)=6$. Prove that, if $P(n)$ is even, then $10^{P(n)/2}+1$ is divisible by $n$.

My approach so far has been to note that $$\frac{1}{n}=\frac{\varphi}{10^{P(n)}-1}\tag{1}$$ Where $\varphi$ is the repeating digits of the decimal expansion, for $n=7$, $\varphi=142857$ for example.

The problem can also be thought as proving $$a=\frac{10^{P(n)/2}+1}{n}\tag{2}$$ is an integer

Substituting (1) in (2) gives $$a=\varphi \frac{10^{P(n)/2}+1}{10^{P(n)}-1}$$ if $P(n)=2T$, then $$a=\varphi \frac{10^{T}+1}{10^{2T}-1}$$ $$a=\varphi \frac{10^{T}+1}{(10^{T}-1)(10^{T}+1)}$$ $$a=\frac{\varphi}{10^{T}-1}$$ But I've not been able to go further than that on how to prove $a$ is an integer.

$\endgroup$
8
  • 1
    $\begingroup$ What are the sqrt's of 1, modulo $n$ ? $\endgroup$ Jul 26, 2021 at 19:00
  • $\begingroup$ Sorry, but I don't quite understand your question. $\endgroup$
    – ordptt
    Jul 26, 2021 at 19:05
  • $\begingroup$ Fermat's little theorem and modular sqrt's $\endgroup$ Jul 26, 2021 at 20:10
  • 1
    $\begingroup$ How do you define the period of $1/n$ for composite $n$ which is not a prime power $p^k$ with $p\ne 2,5$? For example, what is $P(6)$?; $1/6=0.16666\ldots=0.1\bar 6$ $\endgroup$ Jul 26, 2021 at 20:10
  • 2
    $\begingroup$ When $\gcd(n,10)=1$ we have $P(n)$ is the multiplicative order of $10 \bmod n$. $\endgroup$
    – lhf
    Jul 26, 2021 at 22:20

2 Answers 2

2
$\begingroup$

That is not generally true.


Consider $n=21$ then $$\frac{1}{21}=0.\overline{047619}$$ thus $P(21)=6$. However $$10^3+1\equiv 14 \pmod{21}$$


Another example is $n=13\cdot17=221$, then $P(221)=48$ and $$10^{24}+1\equiv 119 \pmod{221}$$


However, the statement is true if $n$ is prime, different from $2$ or $5$. This is because $P(n)=ord_{n}(10)$ (from the definition of multiplicative order, also see this post and this). From $(1)$ in your post $$10^{P(n)} \equiv 1 \pmod{n} \Rightarrow n\mid \left(10^{\frac{P(n)}{2}}+1\right)\cdot\left(10^{\frac{P(n)}{2}}-1\right)$$ Using Euclid's lemma, if we assume $n \mid 10^{\frac{P(n)}{2}}-1$, then $\frac{P(n)}{2}\geq ord_n(10)=P(n)$ which is a contradiction. As a result $$n\mid 10^{\frac{P(n)}{2}}+1$$

$\endgroup$
2
$\begingroup$

In terms of number theory the practical definition of $P(n)=w$ is that $w$ is the smallest natural number so that $10^w\equiv 1\pmod n$. For there to be any such number requires that $\gcd(n,10) = 1$.

(You can mechanically see the equivalence with the periodic length of the decimal expression of $\frac 1n$ because... well, as you put it $\frac 1 n= \frac \varphi{10^{P(n)} - 1}$ and so $10^{P(n)}= \varphi\cdot n + 1$. And we determine what $P(n)$ is by successively finding the remainders for $10\times\text{previous remainder}\div n$. If we ever get back to a remainder of $1$ we have an infinite loop and we are done and so if that takes $w$ times, that's the length of the decimal period and that is the first time that $10^w\equiv 1 \pmod n$)

So if $P(n) = 2m$ is even that means then $10^{2m}\equiv 1\pmod n$ but for all $k: 0< k< 2m$, $10^k\not \equiv 1 \pmod n$

Let $10^m \equiv b\pmod m$ with $b\not\equiv 1\pmod n$.

Then $10^{2m} \equiv b^2 \equiv 1 \pmod n$.

$b^2 -1 \equiv 0 \pmod n$ and

$(b-1)(b+1)\equiv 0\pmod n$.

$\gcd(b-1, b+1) = \begin{cases} 1\\2\end{cases}$ but $\gcd(n,2)=1$ so either we have $n|b-1$ or $n|b+1$. And as $10^m\equiv b\not\equiv 1 \pmod b$ we must have $n|b+1$.

So $b+1 \equiv 10^m + 1 \equiv 0 \pmod n$.

So $n$ divides $10^m+1 = 10^{\frac {P(n)}n} + 1$.

.......

This ties into the stuff we used to do in the fifth grade.

$\frac 1n = 0.a_1a_2....a_{2m}....$ so $10^{2m}\cdot \frac 1n = a_1a_2....a_{2m}.a_1a_2....a_m....$

So $10^{2m}\frac 1n-\frac 1n = a_1a_2....a_{2m}$ so $n|10^{2m}-1$.

If we multiplied $\frac 1n$ by $10^m + 1$ we'd get

$(10^m + 1)\frac 1n = a_1a_2....a_m.a_{m+1}...a_{2m}a_1a_2...a_m..... +0.a_1a_2....a_m....=$

$a_1a_2...a_m + (0.a_{m+1}...a_{2m}a_1a_2...a_m..... +0.a_1a_2....a_m....)$.

So if we can prove that $0.a_{m+1}...a_{2m}a_1a_2...a_m..... +0.a_1a_2....a_m.... = 1$ we'd be done.

Now if we go back to the fifth grade and do that-- $1\div n = 0$ with $1$ remainder; so we multiply by $10$ and $10\div n = a_1 $ with $r_1$ remainder and we multiply by $10$ and $10r_1\div n = a_2$ with $r_2$ remainder-- stuff we used to do, we'd find that in order for $0.a_{m+1}...a_{2m}a_1a_2...a_m..... = 1-\frac 1n =\frac {n-1}n$ while $0.a_1....a_{2m} = 1$ we'd need to have our remainder after $m$ steps would need to be $r_m=n-1$.

(For example. To calculate $\frac 17 = 0.142587....$ we have $10 = 1*7 + 3$ so $a_1 =1; r_1=3$; $30 = 4*7 + 2$ so $a_2 =4; r_2 =2$; $20=2*7 + 6$ so $a_3=2$ and $r_3 = 6 = 7-1$!; $60=7*8 + 4$ so $a_4=8; r_4=4$; $40=7*5+5$ so $a_5=5;r_5=5$ and $50 =7*7+1$ so $a_6=7$ and $r_6 = 1=r_0$ and we are back to the beginning.)

(And its actually kind of neat: If we punch $\frac 67$ into a calculator we get $0.857142.....$ a quasi-transposition of $\frac 17 = 0.142857....$. I can honestly say I had never noticed this before.)

To show that this actually is and must be the case: If we $\frac 1n$ generate the digits $a_1, ....., a_{2m}$ and the remainders $r_1, ...., r_{2m} = 1$. We can in an analogous argument to the above realize that.

$10^{m}= [a_1....a_m]\times n + r_m$ (where $[....]$ is the number made by concatenating the digits) and

$r_m\times 10^m = [a_{m+1}....a_{2m}]\times n + 1$ and

$10^{2m} = [a_1...a_{2m}]\times n + 1$.

So $r_m\times 10^m = (r_m[a_{m+1}....a_{2m}])\times n + r_m^2 = [a_{m+1}....a_{2m}]\times n + 1$.

So $r_m^2 \equiv 1 \pmod n$ and .... it's just like above.

$\endgroup$
4
  • $\begingroup$ Thank you! But why "for all $k: 0< k< 2m$, $10^k\not \equiv 1 \pmod n$"? That's the only part which I didn't quite get why. $\endgroup$
    – ordptt
    Jul 27, 2021 at 18:11
  • 1
    $\begingroup$ Because that is the definition of $P(n)$. Isn't it? If you check $10^k \mod n$ for all $k$ as soon as you get an $w$ so that $10^w \equiv 1 \pmod n$ you are done and $P(n) = w$. And for all the values $k< w$ you do not get $10^k\equiv 1 \pmod n$.... Note $10^{w}\equiv 1\pmod n$ if and only if $P(n)$ divides $w$. If $1 < k < P(n)$ the $P(n)$ doesn't divide $k$ and $10^k\not\equiv 1 \pmod n$. $\endgroup$
    – fleablood
    Jul 27, 2021 at 18:38
  • $\begingroup$ I think there is an error in your argument, around "so either we have". That is generally true for primes (Euclid's lemma). In any case, I found a few contradictions. $\endgroup$
    – rtybase
    Jul 27, 2021 at 21:59
  • 1
    $\begingroup$ Yeah, you are right. But it's even easier then you or I made it. $n$ divides $10^{P(n)} - 1 = (10^{\frac {P(n)}2} + 1)(10^{\frac {P(n)}2} -1)$. If $n$ is prime then $n$ divides one of those and as $10^{\frac{P(n)}2}\not \equiv 1\pmod n$ we don't have $n|10^{\frac{P(n)}2}-1$. My mistake was assuming it was true and trying to prove that $n$ can have components dividing both.... Clearly $n$ dividing the product of relatively numbers doesn't mean relatively prime divisors of $n$ can't divide each of the terms but.... I wanted an answer so I slipped up on that. $\endgroup$
    – fleablood
    Jul 28, 2021 at 3:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .