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.
Solution 1:
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$.
Solution 2:
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$.
Solution 3:
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$.
Solution 4:
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}. $$
Solution 5:
The number $\dfrac{1}{293}$ is the following in its decimal form:
Image Courtesy: Wolfram | Alpha