Find n such that (3^n)≡ 22 mod 31

Note that 22 = -9 = -1 * 3^2 (mod 31).

So, we need to solve 3^n = -1 * 3^2 (mod 31)
==> 3^(n-2) = -1 (mod 31).

Next, note that 3^30 = 1 (mod 31) by Fermat's Little Theorem,
==> 3^15 = -1 or 1 (mod 31), since 31 is prime.

However, it's easily checked that 3^15 = -1 (mod 31).
In fact, 3 is a primitive root mod 31; that is 3^k ≠ 1 for k = 1, 2, ..., 30.

So, 3^(n-2) = 3^30 (mod 31)
==> n - 2 = 15 (mod 30), since 3 is a primitive root mod 31. (The 30 is from Fermat).
==> n = 17 (mod 30).

I hope this helps!

n = 17 works.

Using brute force, the remainders r for each n are as follows:

n r
-----
0 1
1 3
2 9
3 27
4 19
5 26
6 16
7 17
8 20
9 29
10 25
11 13
12 8
13 24
14 10
15 30
16 28
17 22

Note that, for example, with remainder 25 for n = 10, to find the remainder for n = 11
we just need to find the remainder of 3*25 mod 31, which will be 75 - 2*31 = 13. The
whole process didn't take long but I'm glad it stopped at n = 17. :)

Edit: Yes, I am looking for a more efficient way. Note that by Fermat's Little
Theorem we have that 3^31 = 3 mod 31, so since 3^1 = 3 mod 31 I knew I would
get into a 'loop' by at most n = 31, so I knew brute force wouldn't take forever.