# How to find Remainder of this expression?

Tags:
1. Nov 11, 2014

### 22990atinesh

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. Nov 11, 2014

### ehild

32 = x mod 6. What is x?

What is the remainder mod 6 if you square 32?

3. Nov 11, 2014

### Joffan

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.

4. Nov 13, 2014

### Joffan

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
5. Nov 16, 2014

### 22990atinesh

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$

6. Nov 16, 2014

### Joffan

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.

7. Nov 17, 2014

### 22990atinesh

See this lecture at 9:00. What does she trying to say I didn't understand

8. Nov 17, 2014

### Joffan

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$

9. Nov 23, 2014

### 22990atinesh

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

10. Nov 23, 2014

### haruspex

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?

11. Nov 24, 2014

### Joffan

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.