anyone know a way to calculate this?(math)

[almostbusto]

5184^151200 mod 262063

i don't know any shortcuts [img]/images/graemlins/frown.gif[/img]

the answer would be appreciated. but i am much more interested in the short cut around a brute force calculation

[BluffTHIS!]

Paging pzhon.

[arahant]

sounds like a number theory class. shouldn't the method be what you are currently learning?

or does this problem actually have a practical application

[almostbusto]

not for class. just running an algorith manually.

anyway the number SHOULD be equivalent to 2^10! mod 262063
if that is easier to solve

[JayTee]

217056, sorry no help with working it out.

[bigpooch]

262063 is just the product of two primes 521 and 503. Thus,
looking at mod 262063 is simply looking at mod 521 and
mod 503.

One can use Fermat's little theorem:

For any prime p, and a not divisible by p, a^(p-1) is
congruent to 1 mod p.

5184 is congruent to -26 mod (521) (or 495 mod (521) and
congruent to 154 mod (503). Thus, 5184 is not divisible by
any of the two primes and the theorem applies.

151200 is congruent to 400 mod (520)
and congruent to 98 mod (502).

Thus, by the theorem,

a) 5184^151200 is congruent to (-26)^400 mod 521.
b) 5184^151200 is congruent to (154)^98 mod 503.

I don't have a computer program for this, but a calculator,
so I hope I am not making any errors! One idea is just to
evaluate the binary expansion of the exponents and keep
squaring the results to get for the appropriate integers k

(-26)^(2^k) mod 521 and
(154)^(2^k) mod 503.

Then with the binary of the exponents, one simply multiplies
the appropriate terms.

a) (mod 521)
(-26)^4 is congruent to 59 so a) is congruent to 59^100
(59)^4 is congruent to -57 so a) is congruent to (-57)^25
or -(57)^25.
(57)^5 is congruent to 98.
(98)^5 is congrent to 201...so (-57)^25 is congruent to -201
or 320 mod 521.

Thus 5184^151200 is congruent to 320 mod 521.

b) (mod 503) [ use the symbol ~ as congruent to ]
154^98 ~ 75^49

49 is 110001 in binary or 32+16+1

75^2 ~ 92
75^4 ~ 92^2 ~ -87
75^8 ~ (-87)^2 ~ 24
75^16 ~ 73
75^32 ~ 299

so multiplying 299*73*75 (mod 503) yields 263 (mod 503)

5184^151200 is congruent to 263 (mod 503).


If x = 521m+320 is also congruent to 263 (mod 503), then
18m+320 ~ 263 or 18m ~ -57. Note that 18*28 ~ 1, so we can
simply multiply both sides of 18m ~ -57 by 28 to get
m = 28*(-57) = -1596.

Thus, x is congruent to -831196 mod 262063 or

x is congruent to 217056 (mod 262063).

Anyone care to check this? I've already changed this once!

[bigpooch]

Also, 2^(10!) mod 521 is the same as 2^240 mod 521
and 2^(10!) mod 503 is the same as 2^344 mod 503.

240=128+64+32+16 (or is 11110000 in binary)
344=256+64+16+8 (or 101011000 in binary)

so there are only four multiplications for each case after
finding all the results from "squaring".

I've checked that indeed

2^(10!) is congruent to 320 mod 521
and congruent to 263 mod 503.

[bigpooch]

It's best to clarify how to do this in general.

If you are generally trying to compute

x ~ a^s (mod m) [here, I'll use ~ as the congruence
relation], you need to be able to either factorize m into
its canonical prime factorization (product){p[j]^r[j]} or
know phi(m) where phi is the Euler totient function.

The more general theorem (of which Fermat's little theorem
is just a specific case for prime moduli) is that if m is
an integer >1, and a is coprime to m, then

a^phi(m) ~ 1 (mod m).

If you only know phi(m), then one can only say
x ~ a^t (mod m) when t ~ s (mod phi(m)).

But often, you would like to know at least some of the
factors of m.

KNOW prime factors of m
--------------------------

If you have the canonical factorization, let m[j]=p[j]^r[j].

Then if b[j] ~ a (mod m[j]) and if n[j] = phi[m[j]] =
(p[j]-1)*p[j]^(r[j]-1) (a well-known property of phi for
prime powers),

x ~ b[j]^t[j] (mod m[j]) as long as s ~ t[j] (mod n[j]).

You can use whatever computer functions to determine the
set of equations

x ~ x[j] mod (m[j]) for all j.

Here, the x[j] are just computed so that they are "small"
and you may want to have them either between 0 and m[j]-1
or between -m[j]/2 and m[j].

Then, by the Chinese remainder theorem, since the m[j] are
coprime, there exists a unique equivalence class mod m.

A summary of how to find this solution is in the linked
article below:

http://en.wikipedia.org/wiki/Chinese_Remainder_Theorem

[almostbusto]

thanks for the info. not really helpful my specfic situation since, for what i need it for, i needed to assume the modulus can not be factor.

[lightw1thoutheat]

the 'dumb' ( no offense) way would be to do it by successive squaring.

you know 5184=5184 mod 262063
5184^2=143430

find 5184^4 or (5184^2^2) by squaring 143430 and reducing mod 262063

then continue until you get 5184^2^17

since 2^17< 151200 <2^18


5184^151200=5184^2^17 * 5184^2^14 * 5184^2^11 * 5184^2^10 * 5184^2^9 * 5184^2^7 * 5184^2^5

so from your list of numbers multiply these together a few at a time and reduce mod 262063. when you have multiplied all of them, reduce again.