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!

How to find Remainder of this expression?

  1. Nov 11, 2014 #1
    1. The problem statement, all variables and given/known data
    Q. How to find Remainder of the following expression
    ##32^{32^{32}}\mod{}6=?##

    2. Relevant equations

    3. The attempt at a solution
    ##32^{32}\mod{}2=0 \implies 32^{32}=2x##
    ##32^{32}\mod{}3=1 \implies 32^{32}=3y+1##
    would it help to find the remainder of ##32^{32^{32}}\mod{}6##
     
  2. jcsd
  3. Nov 11, 2014 #2

    ehild

    User Avatar
    Homework Helper
    Gold Member

    32 = x mod 6. What is x?

    What is the remainder mod 6 if you square 32?
     
  4. Nov 11, 2014 #3
    You need to work bottom-up for these. As ehild implies, this particular calculation comes out easily and quite quickly.

    For something generic like (pause to generate random numbers...) ##33^{25^{47}} \mod 19##, working out the cycles for each layer needs a little more accounting.
     
  5. Nov 13, 2014 #4
    Start by exploring what ##32^x \mod 6## looks like for low values of x - and this 32 is the bottom one - and then decide what we need to know about the rest of the stack.

    ##32^1 \mod 6 = y = ?##
    ##32^2 \mod 6 = y^2 \mod 6 = ?##
    ##32^3 \mod 6 = y^3 \mod 6 = ?##
    etc. until you discover a cycle - which will be less than 6 long, because there are only so many numbers to work with mod 6.

    Then you can decide what multiples you're looking for in the next exponent up.
     
    Last edited by a moderator: Nov 14, 2014
  6. Nov 16, 2014 #5
    What I'm trying to say is that

    ##32^k; k = 32^{32}##
    where k is a multiple of 2 and 3 as

    ##32^{32} \mod 2 =0 ##
    ##32^{32} \mod 3 = 1##

    on the basis of that how can we figure solve ##32^{32^{32}} \mod 6##
     
  7. Nov 16, 2014 #6
    Yes - what I'm trying to say is that you are starting at the wrong end of this problem. And I don't think that decomposing the 6 into its constituent primes is helping you - rather the reverse - assuming that's what you are doing.

    Start by looking at the behaviour of ##32^n \mod 6## for small n, and that will guide you to ask the right questions about the next exponent up. Your results may be useful, or they may not, but you don't really know until you investigate how 32 behaves (mod 6) under repeated multiplication.
     
  8. Nov 17, 2014 #7
    See this lecture at 9:00. What does she trying to say I didn't understand
     
  9. Nov 17, 2014 #8
    OK... I think, basically, she is working from the idea that ##32^{32^{32}}## is 0 mod 2 and is also 1 mod 3. For any number ##Z## , ##Z = 0 \mod 2 ## and ##Z= 1 \mod 3## completely constrains the value of ## Z \mod 6## . So she is extending a result she already calculated.

    I don't like the tricks she uses in some of these, because they seem to rely a lot on being impressive by already knowing the answer. So she suddenly produces some characterisation of a number that happens to work, but doesn't explain why she chose that particular way of looking at things. It works, but it doesn't teach understanding.

    For ##31^{32^{33}} \mod 11## for example, I start by getting an understanding of ##31^n \mod 11##:
    $$31^1 \mod 11 = 9\\
    31^2 \mod 11 = 81 \mod 11 = 4\\
    31^3 \mod 11 = 36 \mod 11 = 3\\
    31^4 \mod 11 = 27 \mod 11 = 5\\
    31^5 \mod 11 = 45 \mod 11 = 1$$
    - cycle of length 5

    so, next exponent, I only need to worry about where it is in the above cycle, so what is ##32^n \mod 5##?
    $$32^1 \mod 5 = 2 \\
    32^2 \mod 5 = 4\\
    32^3 \mod 5 = 8 \mod 5 = 3\\
    32^4 \mod 5 = 6 \mod 5 = 1$$
    -cycle of length 4

    And finally ## 33 \mod 4 = 1##
    therefore ##32^{33} \mod 5 = 32^1 \mod 5 = 2##
    and ##31^{32^{33}} \mod 11 = 31^2 \mod 11 = 3##
     
  10. Nov 23, 2014 #9
    I'm sorry I misinterpret it. What she is saying trying to say is this
    let ##k = 32^{32^{32}}##
    ##k \mod 6 = R##

    ##k \mod 2 = 0 \implies k=2 \times x##
    ##k \mod 3 = 1 \implies k=3 \times y + 1##

    But at 9:00 she says "R should be in ##2 \times x## and ##3 \times y + 1## form and hence 4 is ans##". This statement I didn't understand
     
  11. Nov 23, 2014 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    You know the answer must be from 0 to 5, where k = 6n+answer. If k = 2x, what answers can you rule out? If k = 3y+1, what answers can you rule out?
     
  12. Nov 24, 2014 #11
    Simple enumeration of cases will find the answer if necessary for a small modulus like 6

    (x = 0 mod 6) ⇒ (x = 0 mod 2) and (x = 0 mod 3)
    (x = 1 mod 6) ⇒ (x = 1 mod 2) and (x = 1 mod 3)
    etc.

    For a more general problem of
    x = a mod m
    x = b mod n
    gcd(m,n) = 1
    Find (x mod mn)​
    ... it is interesting to try this out and find some better search techniques for yourself, before looking up the Chinese Remainder Theorem.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: How to find Remainder of this expression?
  1. Finding an expression (Replies: 4)

  2. Finding remainder (Replies: 35)

Loading...