1

\begin{align*} 3^0 \equiv 1\mod 7\\ 3^1 \equiv 3\mod 7\\ 3^2 \equiv 2\mod 7\\ 3^3 \equiv 6\mod 7\\ 3^4 \equiv 4\mod 7\\ 3^5 \equiv 5\mod 7\\ 3^6 \equiv 1\mod 7\\ 3^7 \equiv 3\mod 7\\ \end{align*}

Now just focusing on 1, 3, 2, 6, 4, 5, 1.... How to devise a formula to find the next number. Like if 2 is given how to find 6 or if 4 is given how to find 5? I am looking for an explicit function.

user469405
  • 11

3 Answers3

1

Fermat says $3^{6k+r}$mod$7=3^r$mod$7,0\le r \le 5$. Up to $r=5$ the calculation is very simple, no?

Corey
  • 132
0

You just need to multiply by $3$ and take the residue mod $7$. This is because $3^j$ mod $7$ is the same as $3^{j-1}\cdot 3$ mod $7$.

TomGrubb
  • 12,909
  • These were my initial thoughts, but, you aren't really giving a formula; you are giving a recursive relationship. – Nairit Aug 04 '17 at 01:30
  • The OP has the formula; they are just taking powers of $3$. The question states "How to devise a formula to get the next number," which a recursive formula is fine for – TomGrubb Aug 04 '17 at 01:32
  • Thanks to both of you, it was of help. But isn't there a formula where you have an input variable and an output variable? – user469405 Aug 04 '17 at 01:33
  • Yes, technically you are right, but this is obvious by definition. A recursive formula would work, but would probably not help the OP. – Nairit Aug 04 '17 at 01:34
  • As far as I know, there isn't a direct non-recursive formula. What would help is taking the power mod $\phi(7) = 6$. – Nairit Aug 04 '17 at 01:35
  • 1
    I was actually looking for an explicit function. – user469405 Aug 04 '17 at 01:39
  • As far as I know, that is not possible. – Nairit Aug 04 '17 at 01:40
  • @user469405, you wrote in your original post "How to devise a formula to find the next number. Like if 2 is given how to find 6 or if 4 is given how to find 5?"; perhaps this was not the best way to let people know that you were looking for an explicit function. Could you please edit/rephrase your question? – Ian Aug 04 '17 at 01:46
  • Okay sure, I will. – user469405 Aug 04 '17 at 01:56
0

If you don't like modulus calculations, you could use:
For odd $a_k:\quad a_{k+1} = (7-a_k)/2$
For even $a_k:\quad a_{k+1} = 7-a_k/2$

Joffan
  • 39,627
  • Thank you! But how did you devise this? I want to use it for other primitives and modulos. – user469405 Aug 04 '17 at 03:18
  • Yes they work universally, thank you again. I am still curious how you devised it but nevermind. Also, I guess you can not merge them both into one? – user469405 Aug 04 '17 at 03:24
  • Can we find the nth number from a given number directly this way? Like if 3 is given can we get 5 from it given that it is the fourth number below or second number above. – user469405 Aug 04 '17 at 03:30
  • I think it works only for "modulo = 2.factor + 1" like "7 = 2.3 + 1". – user469405 Aug 04 '17 at 03:45
  • Yes, it relies to some extent on $2\cdot 3\equiv -1 \bmod 7$ but also on $7$ being a rather small number, with the inevitable lack of complexity that gives. – Joffan Aug 04 '17 at 05:12
  • Can we have a function to find any element given its position from a given element? Like given 3 and 4 steps down, we get 5. – user469405 Aug 06 '17 at 16:46