1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular arithmetic

  1. Aug 16, 2014 #1
    1. The problem statement, all variables and given/known data
    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

    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.

    2. Relevant equations

    3. The attempt at a solution
    Last edited: Aug 16, 2014
  2. jcsd
  3. Aug 16, 2014 #2
    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]
  4. Aug 16, 2014 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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 am are congruent to b mod n, what equation does give you?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted