Hi,

I am currently working on modular arithmetic and recently I have been investigating on the effects of

exponentiation on the system.It will be helpful if someone can share some ideas on the following problem.

According to the division algorithm:

a= nQ+r,

where a is the dividend,n is the divisor,Q is the quotient and r is the remainder respectively.

Let a,n and r be constants.If a is raised to the power of k,where k is an arbitrary positive integer,

a^k = (nQ+r)^k

By using the binomial theorem,(nQ+r)^k = nQ' + r^k

if n<= r^k< n^2 , the quotient will be increased by 1.

So if r^k =/= n,the division process continues,the initial dividend a^k multiplies by a to the power of m,after that the remainder changes again.In equation form:

(a^k)(a^m) = [n(Q'+1) + (r^k)-n)] [nQ+r^m]

= nQ" + [(r^k) - n](r^m)-n] , the final term is the new remainder.

The process stops if the following is satisfied:

{[(r^e - n)r^b - n]r^c - n}r^d - n (......similarly,could be more terms) = 0

the power of a at which the algorithm stops = e+b+c+d

Rearranging the terms gives:

r^(e+b+c+d) = n + nr^d + nr^c + nr^b + nr^e

Or alternatively,in some occasion,the remainder of a^(e+b+c+d) is the same as the of a,so:

{[(r^e - n)r^b - n]r^c - n}r^d - n = r

r^(e+b+c+d) = r + n + nr^d + nr^c + nr^b + nr^e

My question is:

Is there a way to find the value of e+b+c+d for a given value of a,so that we are able to find the

value of the power of a at which the remainder = 0 or recurs upon dividing by a constant n?

In addition,for a given a,is it true that there must be an interger k such that n|a^k (i.e. r = 0) ?

That is:

r^(e+b+c+d) = n + nr^d + nr^c + nr^b + nr^e

where k = e+b+c+d

Example:

I know it is quite messy,I hope it will make it easier to understand by giving an example:

Let a = 11,n = 7

so if Q = 1,r = 4 ( 11 = 7(1) + 4 )

and a^2 = 121,keeping n to be constant yields:

121 = 7(17) + 2, r = 2

For a particular value of a,is there any method to find the power to a at which r recurs(i.e. the remainder = 4 again) and/or r = 0 ?

If there is any mistake please point out,and thanks for reading the wordy paragraphs.