# Prove $10^{P(n)/2}+1$ is divisible by $n$

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.

• What are the sqrt's of 1, modulo $n$ ? Jul 26, 2021 at 19:00
• Sorry, but I don't quite understand your question. Jul 26, 2021 at 19:05
• Fermat's little theorem and modular sqrt's Jul 26, 2021 at 20:10
• 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$ Jul 26, 2021 at 20:10
• When $\gcd(n,10)=1$ we have $P(n)$ is the multiplicative order of $10 \bmod n$.
– lhf
Jul 26, 2021 at 22:20

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$$

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.

• 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. Jul 27, 2021 at 18:11
• 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$. Jul 27, 2021 at 18:38
• 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. Jul 27, 2021 at 21:59
• 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. Jul 28, 2021 at 3:58