0

I am new to Abstract Algebra, and in the 5th edn. of the book by Hillman, Alexanderson have come across the below question #25 in section 1.2.

For each of the following integers d, find the smallest positive integer n such that $d|(10^{n} - 1).$

(a) d = 7,

(b) d = 11,

(c) d = 13,

(d) d = 37,

(e) d = 77,

(f) d = 91,

(g) d = 407.

I am unable to make sense in the introductory chapter of this question. If could provide some link to solve, then would be highly welcome.

jiten
  • 4,524

1 Answers1

0

Hint. By Little Fermat's theorem, if $gcd(d,10) = 1$, then $d$ divides $10^{\varphi(d)}-1$ where $\varphi$ is the Euler's totient function. The smallest positive integer $n$ such that $d$ divides $10^{n}-1$ is called the multiplicative order of $10$ modulo $d$ and it is a divisor of $\varphi(d)$.

(a) For $d=7$, $\varphi(7)=7-1=6$ and $10^3-1=999$ is not divisible by $7$. So the order of $10$ modulo $7$ is $6$.

(b) For $d=11$, $\varphi(11)=11-1=10$. Note that $10^2-1=99$ is divisible by $11$, then the order of $10$ modulo $11$ is $2$.

(c) For $d=13$, $\varphi(13)=12$. We have that $10^2-1=99$, $10^3-1=999$, $10^4-1=9999$ are not divisible by $13$, but
$$10^6-1\equiv (-3)^6-1=(-27)^2-1\equiv (-1)^2-1=0\pmod{13},$$ hence the order of $10$ modulo $13$ is $6$.

Are you able to go on?

Robert Z
  • 145,942
  • Thanks, but not clear with the interpretation in particular. I am unable to conclude anything except that there is no solution. But, the book gives the answer as: 6 for the part (a). So, as per book the smallest value is $10^{6}$ -1. So, how to arrive at the answer is a further issue. ā€“ jiten Oct 25 '17 at 18:57
  • 1
    The Little Fermat's theorem tells you that $10^6-1$ is divisible by $7$. The largest proper divisor of $6$ is $3$, and $10^3-1=999$ is not divisible by 7. So the smallest positive integer $n$ such that $d$ divides $10^nāˆ’1$ is $6$. ā€“ Robert Z Oct 25 '17 at 19:09
  • Thanks for elaborating. However, the book has answer for (b) as 2; but has answer of 6 for part (c), even though 13 is also a prime like 11. Similarly, for part (d) the answer is 3. I feel confused a lot. Please guide. ā€“ jiten Oct 25 '17 at 19:14