Lagrange's theorem

**tukilala** · June 21st 2009, 02:10 PM

Z6={1,2,3,4,5,} (modulo 6) the action * - is multiply. n=|Z|
By Lagrange's theorem - for every number that belong to Z6 (lets say x). so x^n sepopse to be the neutral number. so x^n sepose to be 1.
but 5^5=3125 -> 3125/6=3120 -> 3125-3120=5 -> 5^5 (modulo 6) ≠ 1
same with the other numbers....

so what am i doing wrong???

**skeeter** · June 21st 2009, 02:23 PM

Originally Posted by tukilala

Z6={1,2,3,4,5,} (modulo 6) the action * - is multiply. n=|Z|
By Lagrange's theorem - for every number that belong to Z6 (lets say x). so x^n sepopse to be the neutral number. so x^n sepose to be 1.
but 5^5=3125 -> 3125/6=3120 -> 3125-3120=5 -> 5^5 (modulo 6) ≠ 1
same with the other numbers....

so what am i doing wrong???

$Z_6 = \{0,1,2,3,4,5\}$

order is $6$ ... $5^6 = 15625 \equiv 1(mod \, 6)$

**tukilala** · June 21st 2009, 02:49 PM

ok
and what about Z6 /{0}?
so now it's have 5 elements
Z6/{0} = {1,2,3,4,5}
order is 5... 5^5 (modulo 6) ≠ 1

**Bruno J.** · June 21st 2009, 04:30 PM

$\mathbb{Z}_6^\times$ is not a group under multiplication. There are no inverses to 2 and 3.

$\mathbb{Z}_n^\times$ is a group if and only if n is prime. In that case it has order p-1 and indeed you can check that $a^{p-1}\equiv 1 \mod p$ for all $a$ not divisible by p. This is what Fermat's "little theorem" says; it's actually a very specific case of Lagrange's theorem.

**tukilala** · June 21st 2009, 10:42 PM

lets say that i need to find the last 3 digit of the number: 998^1010
i know that to find the last 3 digits, i need to use modulo 1000
so im looking at the group Z1000 under multiplication, right?
and now: 998^1000 = 998^(999+11) = (998^999)*(998^11)
is it true to say that 998^999 = 1 (by Lagrange's theorem)?? if yes, so why in the group Z6/{0} = {1,2,3,4,5} under multiplication 5^5≠1 (mod 5). 1000 is not a prime number, so why in this case Lagrange's throrem works?

any way, if its true to say that( and i dont understant yet why) so 998^11 = -2^11 = 1024*(-2) = -48 = 952 (mod 1000)
so the last 3 numbers are:952

so when i can use Lagrange's theorem and when not?

**Bruno J.** · June 22nd 2009, 03:52 AM

Originally Posted by tukilala

lets say that i need to find the last 3 digit of the number: 998^1010
i know that to find the last 3 digits, i need to use modulo 1000
so im looking at the group Z1000 under multiplication, right?
and now: 998^1000 = 998^(999+11) = (998^999)*(998^11)
is it true to say that 998^999 = 1 (by Lagrange's theorem)?? if yes, so why in the group Z6/{0} = {1,2,3,4,5} under multiplication 5^5≠1 (mod 5). 1000 is not a prime number, so why in this case Lagrange's throrem works?

any way, if its true to say that( and i dont understant yet why) so 998^11 = -2^11 = 1024*(-2) = -48 = 952 (mod 1000)
so the last 3 numbers are:952

so when i can use Lagrange's theorem and when not?

Did you read my post? That is not a group.

**Swlabr** · June 22nd 2009, 04:37 AM

Originally Posted by tukilala

998^1000 = 998^(999+11) = (998^999)*(998^11)
is it true to say that 998^999 = 1 (by Lagrange's theorem)??

$998^{999} \equiv 312 mod 1000$ ...as Bruno said, using multiplication modulo $n$ , Lagrange's theorem holds if and only if $n$ is prime. In this case we call it "Fermat's Little Theorem".

I always double check my working in such problems with a calculator. Here the numbers are big so I used Maple, but you could try either Wolfram Alpha or the calculator function on google (although I couldn't get google to work for this example).

**tukilala** · June 22nd 2009, 04:56 AM

Wolfam Alpha is nice..
but when im doing a test, i dont have this web site to calculate for me those numbers...
so how can i calculate
998^999 (mod 1000)
without internet
??

**Swlabr** · June 22nd 2009, 10:57 PM

Originally Posted by tukilala

but when im doing a test, i dont have this web site to calculate for me those numbers...

No, but the "trick" is to get so well versed in such questions as to, eventually, not need such a program.

Originally Posted by tukilala

so how can i calculate
998^999 (mod 1000)
without internet
??

I think the answer to this is: not easily.

Note that $1010$ is even and so $2^{1010} = (-2)^{1010}$ .

Hint: prove that $2^3(2^{100}-1) \equiv 0 mod 1000$ (note that $24=3*8$ ).

The problem with this solution is that this hint was not easy to either "see" or prove without a calculator.

There may be a more elegant answer, but that's the best I can conjure up at the moment.

Thread: Lagrange's theorem

LinkBack

Thread Tools

Display

Lagrange's theorem

Similar Math Help Forum Discussions

using the Lagrange Theorem

Prove Wilson's theorem by Lagrange's theorem

Lagrange's Theorem(?)

Lagrange's Mean Value Theorem

Lagrange Theorem.

Search Tags