2

I want to go from that form $3^{n} \mod 7 $ to something that doesn't use exponent. it says, hint : you should use $ n \mod 7$

I listed the values from $3^0 \mod 7 $ to $ 3^{10} $

$$ 3^0 \mod 7 = 1\\ 3^1 \mod 7 = 3\\ 3^2 \mod 7 = 2\\ 3^3 \mod 7 = 6\\ 3^4 \mod 7 = 4\\ 3^5 \mod 7 = 5\\ 3^6 \mod 7 = 1\\ 3^7 \mod 7 = 3\\ 3^8 \mod 7 = 2\\ 3^9 \mod 7 = 6\\ 3^{10} \mod 7 = 4\\ $$

Then I want to find a way to get to the values with $n \mod 7$

I tryed with $ 3n \mod 7$ , $3 (n-1) \mod 7$ , Also tryed with the gcd(a,n) also tryed with something like $3(n * n) \mod 7$

azimut
  • 22,696
Dave
  • 525
  • 1
    You cannot deduce $3^n\mod 7$ from $n\mod 7$ only. For example, $0\equiv 7\mod 7$, but the values $3^0 \equiv 1$ and $3^7 \equiv 3$ are not identical mod $7$. – azimut Feb 11 '13 at 18:32
  • As @azimut says, you want to consider $n\pmod 6$. You can use Lagrange interpolation to find a $5$th degree polynomial to fit these, but I don't see a nice one. – Ross Millikan Feb 11 '13 at 18:38

1 Answers1

3

Show that the values of $3^n\mod 7$ only depend on the remainder of $n\mod 6$. (Hint: Fermat's little theorem)

Then you can tabulate the values of $3^n \mod 7$ like this: $$\begin{array}{l|llllll}n\mod 6 & 0 & 1 & 2 & 3 & 4 & 5\\\hline 3^n\mod 7 & 1 & 3 & 2 & 6 & 4 & 5\end{array}$$

azimut
  • 22,696