Online Course Discussion Forum

Math Challenge II-A Number Theory

 
 
Picture of Neo Liang
Math Challenge II-A Number Theory
by Neo Liang - Sunday, June 30, 2019, 6:49 PM
 

Lecture 6, problem 6.7

My answer for this problem is 1 because a1=1, a2=3, a3=6, a4=1    in mod 7. Since 10=3·3+1, a10=a1=1.

The answer says that it should be 6, so I don't know which one is correct.

 
Picture of Areteem Professor
Re: Math Challenge II-A Number Theory
by Areteem Professor - Tuesday, July 9, 2019, 11:41 AM
 
Note the repeating pattern of the values of $a_n \pmod{7}$ is not $1, 3, 6, 1, 3, 6, \dots$.


$\pmod{7}$ the first few terms of the sequence are: $$a_1 = 1 \equiv 1, a_2 = 3^1 = 3 \equiv 3, a_3 = 3^3 = 27 \equiv 6, a_4 = 3^{27} = 7625597484987 \equiv 6, \dots$$

We can see, in fact, that $a_n \equiv 6 \pmod{7}$ for any $n > 2$:

First note that $3^6 \equiv 1 \pmod{7}$ (by Fermat's Little Theorem), and any power of $3$ is such that $3^n = 3 \pmod{6}$ (for $n \geq 1$). So for all $a_n$ with $n \geq 3$, it is true that $a_n = 3^{6k + 3}$, for some integer $k$ and thus $a_n \equiv \left(3^6\right)^k \times 3^3 \equiv 1 \times 6 \equiv 6 \pmod{7}$. In particular $a_{10} \equiv 6 \pmod{7}$.