General Question

GotJinks's avatar

What is Euler's Theorem?

Asked by GotJinks (29points) May 22nd, 2008
5 responses
“Great Question” (1points)

I am trying to understand what euler’s theorem is and i have looked at wikipedia http://en.wikipedia.org/wiki/Euler’s_theorem but i cant really understand it. Can someone please explain this in a for dummies style please?

Observing members: 0
Composing members: 0

Answers

xyzzy's avatar

Please be more specific, as Wikipedia lists 6 different theorems for Euler, and the link you gave doesn’t point to any specific one.

GotJinks's avatar

In number theory, Euler’s theorem (also known as the Fermat-Euler theorem or Euler’s totient theorem) states that if n is a positive integer and a is coprime to n, then

where φ(n) is Euler’s totient function and ”... ≡ ... (mod n)” denotes congruence modulo n.
The theorem is a generalization of Fermat’s little theorem, and is further generalized by Carmichael’s theorem.
The theorem may be used to easily reduce large powers modulo n. For example, consider finding the last decimal digit of 7222, i.e. 7222 (mod 10). Note that 7 and 10 are coprime, and φ(10) = 4. So Euler’s theorem yields 74 ≡ 1 (mod 10), and we get 7222 ≡ 74×55 + 2 ≡ (74)55×72 ≡ 155×72 ≡ 49 ≡ 9 (mod 10).
In general, when reducing a power of a modulo n (where a and n are coprime), one needs to work modulo φ(n) in the exponent of a:
if x ≡ y (mod φ(n)), then ax ≡ ay (mod n)

xyzzy's avatar

Note that this involves some pretty advanced concepts. The theorem is an observation about how coprimes and modular arithmetic behave.

If a and b are coprime to each other, then there are no common (prime) factors between them other than 1. For example, 4 and 9 are coprime as 4 has factors (2,1) and 9 has factors (3,1).

phi(n) is simply the number of integers from 1..n that are coprime with n. This also tells you how many units are in the ring Z/nZ, which can be though of as the set of integers from 1..n. Let’s take the example n=9. There are the following coprimes:

1,2,4,5,7,8

for each of the above, there is another number where x*y=1 mod 9. For example, 2*5=10=1 mod 9 and 8*8=64=1 mod 9. There is always another number (between 1 and 9 ) that will make it loop around to 1 (or more precisely, equal to the identity element). These are called units.

Euler’s Theorem is that a raised to the power of phi(n) works the same way as long as a and n are coprimes.

If you want me to explain why that is, I haven’t a clue. This is very advanced math and I took only one class of abstract algebra in college a long time ago. Give MathWorld a try.

If you don’t know what a group or a ring is, then whoever is teaching you this is not expecting you to understand why it works; they’re just expecting you to use it like the example shows. And since you tagged the question “calculus”, then I suspect the latter is the case.

(btw, if you can edit the topic tags, replace calculus with “abstract algebra” and/or “number theory”)

xyzzy's avatar

Ugh, after reading what I wrote, I’d say the only useful fact in that mess is the link to MathWorld.

GotJinks's avatar

well thank you for your help

Answer this question

Login

or

Join

to answer.

Mobile | Desktop


Send Feedback   

`