# Calculate the 146th digit after the decimal point of $\frac{1}{293}$

The question is: Calculate the 146th digit after the decimal point of $\frac{1}{293}$

1 / 293 = 0,00341296928.., so e.g., the fifth digit is a 1.

We know that 293 is a prime, probably this would help us. I think an equation involving modulos has to be solved, but I am not sure how to tackle this.

Any help is appreciated! Could perhaps someone give a general method to solve these kind of problems?

EDIT: You are supposed to solve this without using a computer.

-
As a start: $\mathrm{ord}_{293}(10)=146$. –  Guess who it is. Feb 11 '12 at 13:54
The number $146$ seems to be special. It is the period of the decimal expansion of the fraction $\dfrac{1}{293}$. May be somebody shed should light on this! –  user21436 Feb 11 '12 at 13:55
@Kanappan: that's precisely what my comment was saying. The multiplicative order gives the period of a unit fraction with denominator relatively prime to $10$ (which is the base we're considering). –  Guess who it is. Feb 11 '12 at 14:08
I did not follow your comment. Sorry for posting the same thing. And, thanks for the Wolfram Link. –  user21436 Feb 11 '12 at 14:18

Let $r$ be the remainder when $10^{146}$ is divided by $293$. Then the answer is given by the last digit of $(10^{146} - r) / 293$.

Why is this true? Since $1/293$ is a positive number less than one, it is of the form

$1/293 = 0.a_1a_2a_3a_4 \ldots$

and thus

$10^{146}/293 = a_1a_2 \ldots a_{145}a_{146}.a_{147}a_{148} \ldots$

On the other hand, by the division algorithm $10^{146}/293 = q + r/293$, where $q$ is the quotient and $0 \leq r < 293$ is the remainder. Since $q$ is an integer and $0 \leq r/293 < 1$, it follows that $q = a_1a_2 \ldots a_{145}a_{146}$ and $r/293 = 0.a_{147}a_{148} \ldots$.

Then $(10^{146} - r)/293 = q = a_1a_2 \ldots a_{145}a_{146}$.

Thus we can apply modular arithmetic to solve the problem. Notice that

$(10^{146} - r) \cdot 293^{-1} \equiv -r \cdot 293^{-1} \equiv -r \cdot 3^{-1} \equiv -r \cdot 7 \equiv 3r \mod 10$.

Therefore the last digit is equal to $3r \mod 10$.

What remains is to calculate $r$. For this particular case I don't know of any better way than direct calculation. Repeated squaring works, but you might want to use a calculator. It turns out that $10^{146} \equiv 1 \mod 293$, and thus the answer is $3$.

-
Nice explanation. I have added an explanation of how you would do the repeated squaring in my post. –  bgins Feb 11 '12 at 18:32

Consider a rational number $r = \frac{1}{d}$ and suppose it has a decimal expansion of the form $0.\underbrace{d_1d_2\ldots d_m}_{\text{non-recurring}}\underbrace{d_{m+1}d_{m+2}\ldots d_{m+n}}_{\text{recurring}}d_{m+n+1}\ldots$, that is $d_{k+n} = d_{k}$ for $\forall k > m$.

Let $A$ be the integer formed by the first $m$ digits $A = d_1d_2\ldots d_m$, and $B$ be the integer formed by the next $m$ digits $B = d_{m+1} d_{m+2} \ldots d_{m+n}$. Then we have $$10^m r - A = 0.d_{m+1}d_{m+2}\ldots d_{m+n} d_{m+1} d_{m+2} \ldots$$ Multiplying both sides with $10^n$ we get $$10^n (10^m r - A) = B + (10^m r - A)$$ Or, equivalantly $$10^m \left(10^n - 1 \right) = \left( B - A \left(10^n - 1 \right)\right) d$$ This implies that $10^m \left(10^n - 1 \right) \bmod d = 0$.

Since in the case at hand $d$ is relatively prime to $10$, the smallest solutions for $m$ and $n$ are $m=0$ and $n = \operatorname{ord}_{d}(10)$. The multiplicative order is defined as a smallest exponent $n$ such that $10^n \equiv 1 \mod d$. Multiplicative order $\operatorname{ord}_d(10)$ is a divisor of the Euler totient function $\phi(d)$. Since $d = 293$ is prime $$\phi(293) = 293-1 = 292 = 2^2 \cdot 73$$ thus we should try $n = 73$, $n=146$ and then $n=292$. It is not hard to see that $10^{73} = - 1 \bmod 293$, thus $n= 146$.

Having determined that, the 146-th digits equals $B \bmod 10$. $$(10^n-1) = B d$$ meaning that $B \bmod 10 = (-1) d^{-1} \bmod 10 = 3$.

-
Nice explanation! There is a small typo: In a given modulus, the multiplicative order is a divisor of the Euler totient function (not a multiple). –  bgins Feb 11 '12 at 18:27
@bgins Thanks for point out the typo. I have just fixed that. –  Sasha Feb 11 '12 at 19:40

The following is a small variant of the methods of Sasha and Lopsy. We show that $10$ is a quadratic residue of $293$. This enables us to conclude that $10^{146} \not\equiv -1 \pmod{293}$.

It is just a Legendre symbol calculation. For ease of typing we denote the Legendre symbol by $(a/p)$ instead of $\left(\frac{a}{p}\right)$.

Note that $(10/293)=(2/293)(5/293)$. Since $293$ is of the form $8k+5$, we have $(2/293)=-1$.

To calculate $(5/293)$ we use Quadratic Reciprocity. Since one, and indeed both, of $5$ and $293$ are of the shape $4k+1$, $$(5/293)=(293/5)=(3/5).$$ One could continue with Quadratic Reciprocity, but by inspection $(3/5)=-1$. Thus $(10/293)=(-1)(-1)=1$, and we conclude that $10$ is indeed a quadratic residue of $293$.

-

The $146^\text{th}$ digit of $\frac1{293}$ is $$d = \left\lfloor\frac{10^{146}}{293}\right\rfloor - 10 \left\lfloor\frac{10^{145}}{293}\right\rfloor,$$

and sage says it's 3 (sage doesn't count the leading zeros in the decimal mantissa):

(1/293).n(digits=144)


0.00341296928327645051194539249146757679180887372013651877133105802047781569965870307167235494880546075085324232081911262798634812286689419795221843

floor(10^146/293)-10*floor(10^145/293)


3

As to why, well, $p=293$ is prime, and $p-1=292=2^2\cdot73$, and any integer $a$ which is relatively prime to $p$ will have order $d$ dividing $p-1$. So the smallest positive power $d$ of $a=10$ so that $a^d\equiv1\pmod p$ must be $2,4,73,2\cdot73=146$ or, if none of these, then $4\cdot73=292$. Now $d=2$ and $d=4$ can easily be ruled out since $100,1000\not\equiv1\pmod{292}$. For $d=73$, note that $73=(10010001)_2=2^6+2^3+2^0$, so that we can calculate $10^{73}$ modulo $293$ (and its square if necessary) as follows: $$10^2=100$$ $$10^4=(100)^2=10000\equiv38\pmod{293}$$ $$10^8\equiv(38)^2=1444\equiv272\equiv-21\pmod{293}$$ $$10^9\equiv10\cdot(-21)=-210\equiv83\pmod{293}$$ $$10^{18}\equiv(83)^2=6889\equiv150\pmod{293}$$ $$10^{36}\equiv(150)^2=22500\equiv232\equiv-61\pmod{293}$$ $$10^{72}\equiv(-61)^2=3721\equiv205\equiv-88\pmod{293}$$ $$10^{73}\equiv10\cdot(-88)=-880\equiv292\equiv-1\pmod{293}$$

Since squaring the last quantity gives $1$ modulo $293$, we find that $d=\text{ord}_{293}{10}=2\cdot73=146$. This method is called repeated squaring: starting with $a=10$ (step $0$), repeatedly square the result, multiplying again by $a$ (modulo $p$) at each intermediate step $i$ (after squaring) if bit $i$, corresponding to $2^i$ in the binary expansion of $d$, is one.

Now with @m-k's post, we see why. If $10^{146}=q\cdot293+r$, with $q$ and $r$ given by the division algorithm, i.e. $q,r\in\mathbb{Z}$ with $0\leq r<293$, then $q$ is the first quantity in the formula above for $d$: $$q=\left\lfloor\frac{10^{146}}{293}\right\rfloor =\frac{10^{146}-r}{293},$$ and its last digit -- that is, its remainder modulo $10$ -- is equal to $d$: $$d\equiv q\pmod{10}.$$ However, modulo $10$, we have $$293q\equiv-r \pmod{10} \quad \implies \quad q\equiv293^{-1}\cdot-r \equiv-3^{-1}r \equiv-7r \equiv3r \pmod{10}.$$ But we already found that $r=1$, since $10^{146}\equiv1\pmod{293}$, so that $$d\equiv q\equiv 3r\equiv 3\pmod{10}.$$

-
I am not sure if OP would like to see a computer at work. He/She seems to be asking a general method to solve it by hand. Anyway, I'm afraid, it may receive downvotes, while I wont downvot it! –  user21436 Feb 11 '12 at 14:00

The number $\dfrac{1}{293}$ is the following in its decimal form:

Image Courtesy: Wolfram | Alpha

-
In Mathematica, the function RealDigits[] does this quickly. For a ploddingly literal implementation of the method in Mathematica, try First[Nest[QuotientRemainder[10 Last[#], 293] &, {0, 1}, MultiplicativeOrder[10, 293]]]. –  Guess who it is. Feb 11 '12 at 14:10
I don't even have Mathematica installed. May be I'll learn that sooner/later! –  user21436 Feb 11 '12 at 14:19
That's alright. Since you already mentioned Wolfram Alpha, I might as well show how it's actually done in Mathematica (which is the engine behind Wolfram Alpha). –  Guess who it is. Feb 11 '12 at 14:21
I am interested in solving this problem without using a computer. I also have Mathematica installed on my pc. –  ClausW Feb 11 '12 at 14:26
These responses appeared before your edit saying you did not wish to see a computational solution to the problem. I think the downvotes are not fair as a result. –  ncmathsadist Feb 11 '12 at 16:27

This is a 3. The basic period of the decimal expansion looks like this.

0  .0003412969
1.  2832764505
2.  1194539249
3.  1467576791
4.  8088737201
5.  3651877133
6.  1058020477
7.  8156996587
8.  0307167235
9.  4948805460
10. 7508532423
11. 2081911262
12. 7986348122
13. 8668941979
14. 5221843


I computed it using this little program.

apple = 1000
biter = 293
out = ".000"
for k in range(1000):
out += str(apple//biter)
apple %= biter
apple *=10
print out

-