Results 1 to 7 of 7

Math Help - Proving a^b (mod n) ≡ [ a (mod n) ]^b

  1. #1
    Junior Member
    Joined
    Jul 2012
    From
    Earth
    Posts
    56

    Proving a^b (mod n) = [ a (mod n) ]^b

    How would one go about in order to prove

    a^b \mod{n} =\left [ a \mod{n} \right ]^b \, ?

    I would try doing something like this

    a \equiv b \mod{n} \ \Leftrightarrow \ \dfrac{a-b}{n} = k \, , \ \ k \in \mathbb{Z} \, ,

    however I'm not sure how to actually interpret \left [ a \mod{n} \right ]^b. It's periodic function which returns remainders and repeatedly so, what would it's algebraic expression perhaps be?
    Last edited by MathCrusader; August 6th 2012 at 06:35 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jan 2008
    From
    UK
    Posts
    484
    Thanks
    66

    Re: Proving a^b (mod n) ≡ [ a (mod n) ]^b

    Let a=x+kn

    0\le x<n

     x,k,n \in \mathbb{Z}.

    Then you have (x+kn)^b (\mod n) \equiv ((x+kn) \mod n)^b (\mod n)

    Simplify that.
    Last edited by a tutor; August 6th 2012 at 04:01 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,552
    Thanks
    783

    Re: Proving a^b (mod n) ≡ [ a (mod n) ]^b

    Quote Originally Posted by MathCrusader View Post
    How would one go about in order to prove

    a^b \mod{n} \equiv \left [ a \mod{n} \right ]^b \, ?
    Your notation is strange. Either you have a relation x\equiv y\pmod{n} or you have a function x mod n, which returns the remainder when x is divided by n. In the first case, you can't use mod in both sides of the relation. In the second case, you can't use \equiv, or, at least, you need to define it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jul 2012
    From
    Earth
    Posts
    56

    Re: Proving a^b (mod n) ≡ [ a (mod n) ]^b

    Quote Originally Posted by emakarov View Post
    Your notation is strange. Either you have a relation x\equiv y\pmod{n} or you have a function x mod n, which returns the remainder when x is divided by n. In the first case, you can't use mod in both sides of the relation. In the second case, you can't use \equiv, or, at least, you need to define it.
    You are correct, let me fix that.

    Quote Originally Posted by a tutor View Post
    Let a=x+kn

    0\le x<n

     x,k,n \in \mathbb{Z}.

    Then you have (x+kn)^b (\mod n) \equiv ((x+kn) \mod n)^b (\mod n)

    Simplify that.
    Thanks!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2012
    From
    Earth
    Posts
    56

    Re: Proving a^b (mod n) ≡ [ a (mod n) ]^b

    Quote Originally Posted by a tutor View Post
    Let a=x+kn

    0\le x<n

     x,k,n \in \mathbb{Z}.

    Hmm
    Then you have (x+kn)^b (\mod n) \equiv ((x+kn) \mod n)^b (\mod n)

    Simplify that.
    Hm, I would appreciate if you could show me the simplificaton, the multiple mods are confusing me.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jan 2008
    From
    UK
    Posts
    484
    Thanks
    66

    Re: Proving a^b (mod n) ≡ [ a (mod n) ]^b

    Following emakarov's comments perhaps it would be better if we used a % b for the remainder when a is divided by b.

    Then rather than

    (x+kn)^b (\mod n) \equiv ((x+kn) \mod n)^b \  (\mod n)

    we have

    (x+kn)^b\   \%\  n  \equiv ((x+kn)\% \ n)^b \  (\mod n)

    (x+kn)^b\   \% \ n  \equiv x^b  \ (\mod n)

    One last step?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Proving a^b (mod n) ≡ [ a (mod n) ]^b

    if one uses [a] for the remainder of a, upon division by the integer n (where this remainder is between 0 and n-1, inclusive), we can state this as:

    [ab] = [[a]b]. note that [a] is just an integer.

    this can be shown using induction on b:

    for b = 1:

    [a] = [[a]], since 0 ≤ [a] ≤ n-1.

    assume that for b = k,

    [ak] = [[a]k].

    then:

    [ak+1] = [(a)(ak)] = [[a][ak]] (see below)

    = [[a][[a]k]] (by our inductive hypothesis)

    = [[[a]][[a]k]] (by our base case, [a] = [[a]])

    = [[a][a]k] (again, see below)

    = [[a]k+1]

    (the crucial step is this:

    [[x][y]] = [xy].

    note that if x = tn + c, y = un + d, where 0 ≤ c,d < n that:

    xy = (tn + c)(un + d) = (tun + c + d)n + cd. writing cd = wn + f, for 0 ≤ f < n, xy = (tun + c + d + w)n + f,

    so we have:

    [[x][y]] = [cd] = f = [xy]. one can view this as "a rule for brackets and multiplying": remove the outer 2 brackets on each side, and the innermost pair, multiply and add outer brackets).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: June 28th 2010, 08:32 PM
  2. a^p≡1 (mod p^n) iff a≡1 (mod p^(n-1)), n≥2
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 8th 2010, 08:59 AM
  3. lcm of k,k+1,k+2 where k≡3(mod 4)
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 12th 2010, 01:46 PM
  4. x≡y (mod a) => (x,a)=(y,a)
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 7th 2010, 05:05 AM
  5. x^n ≡ 3 (mod 4) only if x ≡ n ≡ 1 (mod 2)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 30th 2010, 04:24 AM

Search Tags


/mathhelpforum @mathhelpforum