Re: 5^n mod 32


maarte wrote:
> Hello everybody,
> one easily sees that 5^n=1+4n mod 16(=2^4), so my question is of there is an analoguous formula mod 32(=2^5)? Thanks in favor.

Further to the other replies, here is my rather laborious attempt at
finding general linear solutions.

Consider the equation

c^n = a*n + b (mod m) (1)

where c, m are any integers > 2. We want, if possible, to find integers
a and b such that this equation holds for all integer n >= 0.

Setting n = 0 in (1) yields

b = 1 (mod m) (2)

Since (1) is true for any n, we also have

c^(n+1) = a*(n+1) + b (mod m) (3)

And multiplying (1) by c gives

c^(n+1) = c*a*n + c*b (mod m) (4)

Then, from (3) and (4),

a*(n+1) + b = c*a*n + c*b (mod m) (5)

or, rearranging,

a*n*(c-1) + b*(c-1) = a (mod m) (6)

For (6) to be true for any n we must have

a*(c-1) = 0 (mod m) (7)
b*(c-1) = a (mod m) (8)

>>From (8) and (2):

c-1 = a (mod m) (9)

So

a = k*m + c-1 (10)

for some integer k.

Substitute (10) into (7):

(k*m + c-1)*(c-1) = 0 (mod m)

which implies that (c-1)^2 = 0 mod m.

Therefore there is a solution only if m divides (c-1)^2. If m DOES
divide (c-1)^2 then a "simple" solution is seen to be

a = c-1 (from (9))
b = 1 (from (2))

In the given case of c = 5, there is a solution if and only if m
divides (5-1)^2 = 16; i.e. for m = 2, 4, 8, 16.

.