Finding the remainder from very large division
mark...@jungle-monkey.com
And I think the answer is 4.
However it would be nice to verify my answer, since most calculators
can't handle numbers that large with any accuracy I am kind of stuck.
I've tried a free online interface to mathematica:
But it does not seem to have any way to find the remainder.
Do you have any suggestions for software or web sites (preferably
free) that I could use to check this (and similar equations)?
Thanks
Arturo Magidin
No, I don't have suggestions for software. I do have suggestions for
you to use your own firmware: your brain...
Try exponentiation by repeated doubling and reducing after each step.
Namely, since 201 = 128 + 64 + 8 + 1 = 2^7 + 2^6 + 2^3 + 2^0, you can
compute
3^201 as 3^{128}*3^{64}*3^8*3.
So, compute 3^2 = 9 modulo 11.
Squaring 3^2 gives you 3^4 = 9^2 = 81 = 4 (mod 11).
Squaring 4 gives you 3^8 = (3^4)^2 = 4^2 = 16 = 5 (mod 11).
Squaring this gives you 3^16 = (3^8)^2 = 5^2 = 25 = 3 (mod 11).
Aha! 3^16 = 3^1 (mod 11), so we get into a cycle now:
3^1 = 3 (mod 11)
3^2 = 9 (mod 11)
3^4 = 4 (mod 11)
3^8 = 5 (mod 11)
3^16 = 3 (mod 11)
3^32 = 9 (mod 11)
3^64 = 4 (mod 11)
3^128 = 5 (mod 11)
So 3^{201} = 3^{128} * 3^{64} * 3^8 * 3^1
= 5 * 4 * 5 * 3 (mod 11)
= 300 (mod 11)
= 3 (mod 11).
--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================
Arturo Magidin
magidin-at-member-ams-org
Dave Seaman
> Thanks
The Mathematica command for this is:
Mathematica 6.0 for Mac OS X x86 (64-bit)
Copyright 1988-2007 Wolfram Research, Inc.
In[1]:= PowerMod[3,201,11]
Out[1]= 3
I don't know whether that web page can reproduce this computation. The
quickest way to verify this without a CAS is to notice that 3^5 == 1 (mod
11), and therefore 3^201 == 3^(5*40) * 3^1 (mod 11) == 3 (mod 11).
--
Dave Seaman
Oral Arguments in Mumia Abu-Jamal Case heard May 17
U.S. Court of Appeals, Third Circuit
<http://www.abu-jamal-news.com/>
quasi
It's a lot easier than that.
By Fermat's little theorem, 3^10 = 1 mod 11.
3^10 = 1 (mod 11) => 3^200 = 1 (mod 11) => 3^201 = 3 (mod 11).
quasi
Arturo Magidin
Thanks, I do know that. However, given the OP's original post, was it
reasonable to think he knew Fermat's Little Theorem?
Also, the procedure I outlined above is of course usable for computing
large modular exponentiations regardless of the modulus, without having
to factor the modulus (or finding some other way of calculating phi(m)
to apply Euler's Theorem).
quasi
(Arturo Magidin) wrote:
Yes -- read the first line of the OP's post.
quasi
Arturo Magidin
quasi <qu...@null.set> wrote:
>On Wed, 28 Nov 2007 20:17:58 +0000 (UTC), mag...@math.berkeley.edu
>(Arturo Magidin) wrote:
>
>>In article <opirk3540sgujl707...@4ax.com>,
>>quasi <qu...@null.set> wrote:
>>>On Wed, 28 Nov 2007 19:51:46 +0000 (UTC), mag...@math.berkeley.edu
>>>(Arturo Magidin) wrote:
>>>
>>>>In article <528e9d88-0e84-4235...@y5g2000hsf.googlegroups.com>,
>>>> <mark...@jungle-monkey.com> wrote:
>>>>>I am trying to use Fermats Theorem to find: 3^201 mod 11
[...]
>>>>>However it would be nice to verify my answer, since most
calculators
[...]
>>Thanks, I do know that. However, given the OP's original post, was it
>>reasonable to think he knew Fermat's Little Theorem?
>
>Yes -- read the first line of the OP's post.
Ouch. Quite right.
Of course, he said he wanted to ->verify<- the answer, rather than to
apply the Theorem. So applying Fermat's Little defeats the purpose:
you don't verify that you applied the theorem correctly by applying
the theorem...
bill
x ^ n mod y is cyclic. Once you discover the cycle, you can
find the mod for any n.
Bill J
.
mensa...@aol.com
> I am trying to use Fermats Theorem to find: 3^201 mod 11
>
> And I think the answer is 4.
>
> However it would be nice to verify my answer, since most calculators
> can't handle numbers that large with any accuracy I am kind of stuck.
Get a better calculator:
Python 2.5 (r25:51908, Sep 19 2006, 09:52:17) [MSC v.1310 32 bit
(Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
IDLE 1.2
>>> print 3**201 % 11
3
>
> I've tried a free online interface to mathematica:
>
> http://www.quickmath.com/
>
> But it does not seem to have any way to find the remainder.
>
> Do you have any suggestions for software or web sites (preferably
> free)
Python is free.
Rob Johnson
Dave Seaman <dse...@no.such.host> wrote:
>On Wed, 28 Nov 2007 11:44:14 -0800 (PST), mark...@jungle-monkey.com wrote:
>> I am trying to use Fermats Theorem to find: 3^201 mod 11
>
>> And I think the answer is 4.
>
>> However it would be nice to verify my answer, since most calculators
>> can't handle numbers that large with any accuracy I am kind of stuck.
>
>> I've tried a free online interface to mathematica:
>
>> http://www.quickmath.com/
>
>> But it does not seem to have any way to find the remainder.
>
>> Do you have any suggestions for software or web sites (preferably
>> free) that I could use to check this (and similar equations)?
>
>> Thanks
>
>The Mathematica command for this is:
>
>Mathematica 6.0 for Mac OS X x86 (64-bit)
>Copyright 1988-2007 Wolfram Research, Inc.
>
>In[1]:= PowerMod[3,201,11]
>
>Out[1]= 3
Or simply use bc from the Terminal and enter
(3^201)%11
>I don't know whether that web page can reproduce this computation. The
>quickest way to verify this without a CAS is to notice that 3^5 == 1 (mod
>11), and therefore 3^201 == 3^(5*40) * 3^1 (mod 11) == 3 (mod 11).
This is my preferred method.
Rob Johnson <r...@trash.whim.org>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
mark...@jungle-monkey.com
> On Nov 28, 1:44 pm, marksm...@jungle-monkey.com wrote:
>
> > I am trying to use Fermats Theorem to find: 3^201 mod 11
>
> > And I think the answer is 4.
>
> > However it would be nice to verify my answer, since most calculators
> > can't handle numbers that large with any accuracy I am kind of stuck.
>
> Get a better calculator:
>
> Python 2.5 (r25:51908, Sep 19 2006, 09:52:17) [MSC v.1310 32 bit
> (Intel)] on win32
> Type "copyright", "credits" or "license()" for more information.
>
> IDLE 1.2>>> print 3**201 % 11
>
> 3
>
Nice did not know python supported such high precision operations.
Phil Carmody
> In article <fikhk6$4qj$1...@mailhub227.itcs.purdue.edu>,
> Dave Seaman <dse...@no.such.host> wrote:
> >On Wed, 28 Nov 2007 11:44:14 -0800 (PST), mark...@jungle-monkey.com wrote:
> >> I am trying to use Fermats Theorem to find: 3^201 mod 11
> >The Mathematica command for this is:
> >
> >
> >Out[1]= 3
>
> Or simply use bc from the Terminal and enter
>
> (3^201)%11
Bletch. Large intermediate value. dc's a much better fit:
3 201 11|p
Test bc's ``3^20000001%11'' against dc's
``3 20000001 11|p'' for a clearer example of why you don't
want to create unnecessarily large intermediates.
Phil
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration
mensa...@aol.com
And, as pointed out by others, you don't need such precision
for THAT problem, but it's nice to have for problems where
you DO need it.
Although you do have to be careful, for although 3**201 is
actually not high at all, the power function is restricted
to 32-bit exponents, so the limit 2**2147483647 won't get
you past the 10th Generation Type [1,2] Mersenne Hailstone
in the Collatz Conjecture.
Robert Israel
Any CAS (Computer Algebra System), or anything that can handle
arbitrary-length integers, should be able to do this with no
trouble at all. For example, in any flavour of unix/linux you can
type
> bc
3 ^ 201 % 11
Among free CAS's, you might try Axiom or Maxima or PARI/GP.
--
Robert Israel isr...@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
Dave Seaman
> (3^201)%11
In Mathematica there can be a huge difference in efficiency between
Mod[a^b,c]
and
PowerMod[a,b,c]
in that the latter form causes reductions to be performed along the way,
instead of computing a^b as a possibly enourmous integer before doing any
reductions mod c.
Does bc have a similar form?
Dik T. Winter
> In article <528e9d88-0e84-4235...@y5g2000hsf.googlegroups.com>,
> <mark...@jungle-monkey.com> wrote:
> >I am trying to use Fermats Theorem to find: 3^201 mod 11
> >
> >And I think the answer is 4.
> No, I don't have suggestions for software. I do have suggestions for
> you to use your own firmware: your brain...
>
> Try exponentiation by repeated doubling and reducing after each step.
>
> Namely, since 201 = 128 + 64 + 8 + 1 = 2^7 + 2^6 + 2^3 + 2^0, you can
> compute
Better, consider Fermat's little theorem: when p is prime,
a^(p - 1) = 1 mod p. That, and Euler's extension, are very useful
for this kind of problems.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Dik T. Winter
...
> >>>> <mark...@jungle-monkey.com> wrote:
> >>>>>I am trying to use Fermats Theorem to find: 3^201 mod 11
...
> >>reasonable to think he knew Fermat's Little Theorem?
> >
> >Yes -- read the first line of the OP's post.
>
> Ouch. Quite right.
So, the question arises why the OP thought the answer was 4 and not 3.
I can not find a way to get at that with any wrong formulation of
Fermat's little theorem. With all the wrong formulations I can come
up with, I find an answer of 5... (I checked a^p = 1 mod p and
a^(p-1) = a mod p.)
William Elliot
> I am trying to use Fermats Theorem to find: 3^201 mod 11
>
> And I think the answer is 4.
>
3^10 = 1 (mod 11)
3^201 = 3 * (3^10)^20 = 3 (mod 11)
> However it would be nice to verify my answer, since most calculators
> can't handle numbers that large with any accuracy I am kind of stuck.
>
It would be nice to not rely upon calculators.
> Do you have any suggestions for software or web sites (preferably
> free) that I could use to check this (and similar equations)?
>
Baloney, the math is simple.
Rob Johnson
Unfortunately not. As Phil Carmody points out, dc does, but I prefer
bc in general due to its programmability. In fact, powermod can be
defined in bc by pasting the following definition into bc
define powermod(a,b,c)
{
auto d;
d = 1;
while (b > 0)
{
while(b%2==0)
{
b = b/2;
a = (a*a)%c;
}
b = b-1;
d = (d*a)%c;
}
return(d);
Sylvain Croussette
ht.
>
> So, the question arises why the OP thought the answer was 4 and not 3.
> I can not find a way to get at that with any wrong formulation of
> Fermat's little theorem. With all the wrong formulations I can come
> up with, I find an answer of 5... (I checked a^p = 1 mod p and
> a^(p-1) = a mod p.)
> --
Maybe the op thought that:
3^201 = 3^(10*20 + 1) = 3^(10*20) + 3^1 mod 11 instead of 3^(10*20) *
3^1 mod 11. This would become (1 + 3^1)=4 mod 11
Qasim
it is a short cut i have developed
consider 3^10=59049
3^10/11=5368.09
so if we multiply 11 by 59048
it can be seen easily that the remainder is 1 in this case
200/10=20
it implies (3^10*3^10.....mod11)=(1*1*...)mod11=1
3^200mod11 will give us remainder 1
then this question is reduced to
3mod11*1mod11=3mod11
3mod11=1 ANS
Please mail me at qasim.h...@gmail.com
if there is some mistake in it..