Results 1 to 7 of 7

Thread: 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

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

    I would try doing something like this

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

    however I'm not sure how to actually interpret $\displaystyle \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; Aug 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 $\displaystyle a=x+kn$

    $\displaystyle 0\le x<n$

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

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

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

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    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

    $\displaystyle a^b \mod{n} \equiv \left [ a \mod{n} \right ]^b \, ?$
    Your notation is strange. Either you have a relation $\displaystyle 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 $\displaystyle \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 $\displaystyle 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 $\displaystyle \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 $\displaystyle a=x+kn$

    $\displaystyle 0\le x<n$

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

    Then you have $\displaystyle (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 $\displaystyle a=x+kn$

    $\displaystyle 0\le x<n$

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

    Hmm
    Then you have $\displaystyle (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

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

    we have

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

    $\displaystyle (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,546
    Thanks
    842

    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: Jun 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: Mar 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: Feb 12th 2010, 01:46 PM
  4. x≡y (mod a) => (x,a)=(y,a)
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Feb 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: Jan 30th 2010, 04:24 AM

Search Tags


/mathhelpforum @mathhelpforum