How to find Remainder of this expression?

[22990atinesh]

Homework Statement

Q. How to find Remainder of the following expression
$32^{32^{32}}\mod{}6=?$

Homework Equations

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$

 

[ehild]

32 = x mod 6. What is x?

What is the remainder mod 6 if you square 32?

 

[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.

 

[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.

 

[22990atinesh]

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.

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$

 

[Joffan]

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$

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.

 

[22990atinesh]

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.

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

 

[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$

 

[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

 

[haruspex]

R should be in ##2×x2 \times x$and$3×y+13 \times y + 1## form and hence 4 is ans

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?

 

[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.