Modular Arithmetic: Exponentiation & Division Algorithm

[davon806]

Homework Statement

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.

Homework Equations

The Attempt at a Solution

 

[Pond Dragon]

The question is confusing. I'll interpret it as follows:

"Suppose we have that [itex]a\equiv b\mod n[/itex]. Can we find an [itex]m[/itex] such that [itex]a^m\equiv 0\mod n[/itex] or such that the remainder remains the same for [itex]m'>m[/itex]?"

The answer is, generally, no. Consider [itex]2\mod 6[/itex]. Then,

[tex]2^2\equiv 4\mod 6 \\ 2^3\equiv 2\mod 6 \\ 2^4\equiv 4\mod 6 \\ \vdots \\ 2^{2k}\equiv 4\mod 6 \\ 2^{2k+1}\equiv 2\mod 6.[/tex]

 

[haruspex]

The question is confusing. I'll interpret it as follows:

"Suppose we have that [itex]a\equiv b\mod n[/itex]. Can we find an [itex]m[/itex] such that [itex]a^m\equiv 0\mod n[/itex] or such that the remainder remains the same for [itex]m'>m[/itex]?"

As I read the question, it's

"Suppose we have that [itex]a\equiv b\mod n[/itex]. Can we find an [itex]m[/itex] such that [itex]a^m\equiv 0\mod n[/itex] or such that the remainder is b? And how to find the smallest such m?"​

As you say, there will not in general be an m that makes the remainder 0. davon806, consider factorisations of a and n.
For the second question, if a and a^m are congruent to b mod n, what equation does give you?