Solved

remainder

Posted on 2006-07-13
11
593 Views
Last Modified: 2010-08-05
           
(32^32^32)/7

what would be the remainder.kindly help.
0
Comment
Question by:shilpi84
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
  • 2
  • +2
11 Comments
 
LVL 27

Expert Comment

by:d-glitch
ID: 17099946
I get 4.
0
 
LVL 27

Accepted Solution

by:
d-glitch earned 150 total points
ID: 17100041
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
 
LVL 4

Expert Comment

by:NicoLaan
ID: 17100156
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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:shilpi84
ID: 17100447
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
 
LVL 27

Expert Comment

by:d-glitch
ID: 17100671
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
 
LVL 27

Expert Comment

by:d-glitch
ID: 17102597
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
 
LVL 4

Assisted Solution

by:NicoLaan
NicoLaan earned 150 total points
ID: 17103774
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
 
LVL 18

Assisted Solution

by:JR2003
JR2003 earned 200 total points
ID: 17104361
(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
 
LVL 18

Expert Comment

by:JR2003
ID: 17104367
I meant:
So the answer from 2) is 4
0
 
LVL 8

Expert Comment

by:hiteshgupta1
ID: 17129310
4 is the correct answer
used windows calc:)
0
 
LVL 4

Expert Comment

by:NicoLaan
ID: 17149050
Thanks!
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

A Guide to the PMT, FV, IPMT and PPMT Functions In MS Excel we have the PMT, FV, IPMT and PPMT functions, which do a fantastic job for interest rate calculations.  But what if you don't have Excel ? This article is for programmers looking to re…
This article seeks to propel the full implementation of geothermal power plants in Mexico as a renewable energy source.
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…

696 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question