Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
As a start: $\mathrm{ord}_{293}(10)=146$. –  J. M. Feb 11 '12 at 13:54
1  
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
2  
@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). –  J. M. 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

6 Answers 6

up vote 12 down vote accepted

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

share|improve this answer
    
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$.

share|improve this answer
    
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$.

share|improve this answer

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

share|improve this answer
    
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:

1/293

Image Courtesy: Wolfram | Alpha

share|improve this answer
    
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]]]. –  J. M. 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). –  J. M. 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
3  
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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.