remainder

           
(32^32^32)/7

what would be the remainder.kindly help.
shilpi84Asked:
Who is Participating?
 
d-glitchConnect With a Mentor Commented:
32 mod 7 = 4

32^2 mod 7   =  4^2 mod 7 = 16 mod 7 = 2
32^4 mod 7   =  2^2 mod 7 =   4 mod 7 = 4
32^8 mod 7   =  4^2 mod 7 = 16 mod 7 = 2
32^16 mod 7 =  2^2 mod 7 =   4 mod 7 = 4
32^32 mod 7 =  4^2 mod 7 = 16 mod 7 = 2

(32^32)^2 mod 7   =  2^2 mod 7 =  4 mod 7 = 4
(32^32)^4 mod 7   =  4^2 mod 7 =16 mod 7 = 2
(32^32)^8 mod 7   =  2^2 mod 7 =  4 mod 7 = 4
(32^32)^16 mod 7 =  4^2 mod 7 =16 mod 7 = 2
(32^32)^32 mod 7 =  2^2 mod 7 =  4 mod 7 = 4
0
 
d-glitchCommented:
I get 4.
0
 
NicoLaanCommented:
Cool question! :-D

32^32^32 = 2 ^ 6 ^ 32 ^ 32 = 2 ^ (6 x 32 x 32) = 2 ^ 5120
I used my windows calculator to check if this trick is correct.

Now how about divided by 7?
google:    arithmetic divided by 7
3rd link, "numbers and codes."
Page 13 and 14 of the PDF

I opened Excel and placed 2, 4, 8 and so on in one column and divided it by 7 in the next column.
See the REMAINDERS below.
2^1 --> 0.285714286
2^2 --> 0.571428571
2^3 --> 0.142857143
2^4 --> Now it repeats!

So now it becomes a question of dividing 5120 / 3 and what is the remainder?
5120 / 3 = 1706.6666
2 / 3 = 0.666666

So 2^5120 / 7 must have a remainder of 0.571428571!!

As additional proof for myself I checked with a small number on the calculator:
Remainder for 2^20 / 7 = 0.571428571
20 / 3 = 6.66666

I'm sure that for some math masters this is obvious but for me this fairly easy solution was a nice suprise.
0
Get expert help—faster!

Need expert help—fast? Use the Help Bell for personalized assistance getting answers to your important questions.

 
shilpi84Author Commented:
my answer is coming out 2 be one.

this is how i worked it out
(28+4)^32^32/7

the last term in binomial expansion wud be 4^32^32.

now,
4^1/7 remainder is 4
4^2/7 remainder is 2
4^3/7 remainder is 1

we observe here cyclicity is 3
so (32^32)/3=(33-1)^32=3x+1

thus we have

4^3x+1/7

this will yeild remainder 1 with x assumed 1

is this approach correct?
0
 
d-glitchCommented:
32 gives a reaminder of 4 mod 7

In mod 7 arithmetic

32^32  =  4^32  =  ((((4^2)^2)^2)^2)^2      ==> Squaring 5 times
The cycle I get is:   2  4  2  4  2    ==>  32^32  = 2 mod 7


Repeat the process once more:

(32^32)^32  =  2^32  =  ((((2^2)^2)^2)^2)^2      ==> Squaring 5 times
The cycle I get is:   4  2  4  2  4    ==>  32^32^32 = 4 mod 7
0
 
d-glitchCommented:
In mod 7 arithmetic:

     32^n  =  4^n

    32^n   =  4^n  =  1   if and only if   n is a multiple of 3

32^32^32  =  (32^32)^32  = 32^(32^2)  =  32^1024      <== There are no factors of 3 in that exponent
0
 
NicoLaanConnect With a Mentor Commented:
shilpi84,

The answer is 4 as d-glitch said. I wrote it as a fraction as you can see. 4/7 = 0.57...

This step is correct.
4^1/7 remainder is 4 (line 1)
4^2/7 remainder is 2 (line 2)
4^3/7 remainder is 1 (line 3)
Your next step I don't understand.
1024/3 has remainder of 1, so you need to take line 1 from above, so 4^32^32 mod 7 = 4.

Did you read the PDF I told you about? It gives a lot of information specifically about this type of problem.
Also with examples and proof about mod n algebra addition and multiplication rules.
http://www.maths.ox.ac.uk/prospective-students/undergraduate/sutton/lecture1.pdf

For me this type of math is new so I took a simple try it and test it approach.
But from what I understand and try myself, d-glitch his story is perfect and also using the rules of this algebra.
My approuch is more figuring it out as I go.
0
 
JR2003Connect With a Mentor Commented:
(32^32^32)

=((2^5)^(32)^(32))

=(2^160)^(32)

=2^5120

You can notice that there is a pattern repeating on the last digit of the numbers when moded with 7:

2^1=2        = 2 mod 7
2^2=4        =4  mod 7
2^3=8        =1  mod 7
2^4=16      =2 mod 7
2^5=32      =4  mod 7
2^6=64      =1  mod 7
2^7=128    =2  mod 7
2^8=256    =4 mod 7
2^9=512    =1  mod 7
2^10=1024 =2  mod 7

You can see there is a pattern that repeats of 2, 4, 1,    2, 4, 1,   2, 4, 1 ....

i.e.
If a number 2^x = 2 mod 7
   Then the number 2^(x+1) = 4         mod 7

If the number 2^x = 4 mod 7
   Then the number 2^(x+1) = 1         mod 7

If a number 2^x = 1 mod 7
   Then the number 2^(x+1) = 2          mod 7

which brings us back to the begining, i.e
If a number 2^x = 2 mod 7
   Then the number 2^(x+1) = 4         mod 7



So if you want to work out what 2^n mod 7 is

Take the result of:  n mod 3:

1) If the answer is 1 then 2^n mod 7 = 2

2) If the answer is 2 then 2^n mod 7 = 4

3) If the answer is 0 then 2^n mod 7 = 1



Now back to the result that 32^32^32 = 2^5120


5120 = 2   mod 3

So the answer from 3) is 4



0
 
JR2003Commented:
I meant:
So the answer from 2) is 4
0
 
hiteshgupta1Commented:
4 is the correct answer
used windows calc:)
0
 
NicoLaanCommented:
Thanks!
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.