Solved

remainder

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

what would be the remainder.kindly help.
0
Comment
Question by:shilpi84
  • 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
Courses: Start Training Online With Pros, Today

Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.

 

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

Gigs: Get Your Project Delivered by an Expert

Select from freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely and get projects done right.

Question has a verified solution.

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

Suggested Solutions

Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! https://www.google.com/about/careers/students/guide-to-technical-development.html How to Know You are Making a Difference at EE In August, 2013, one …
We are taking giant steps in technological advances in the field of wireless telephony. At just 10 years since the advent of smartphones, it is crucial to examine the benefits and disadvantages that have been report to us.
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…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

785 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