HoughtonlakeBoard.org

TIPS & EXPERT ADVICE ON ESSAYS, PAPERS & COLLEGE APPLICATIONS

Introduction

Euler’s
theorem was one of the prompts given to us when we started doing our
explorations. After researching many of the topics, I found that the theorem
had a simple elegance to it that was both complex and simple for me to
understand. The concept of prime numbers was one we were all introduced to at a
young age and I never really understood the full application if this topic.
While exploring Euler’s theorem, I came to understand the significance of these
values in sets and factorisation of large numbers. Euler proved the two-square
theorem and Fermat’s little theorem as well laying the ground work for the
mathematics that later led to the first proof of the four-square theorem. Euler’s
theorem arises in applications of elementary number theory, including the
theoretical underpinning for the RSA cryptosystem1.
In this exploration I want to prove Euler’s theorem and apply it in other
situations to show its value.

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

 

The
Theorem

Euler’s
theorem states: Let n be a positive
integer, and let a be an integer that
is relatively prime to n.

In
number theory, two integers a and b are said to be relatively prime, mutually
prime, or coprime if the only positive integer (factor) that divides both of
them is 1.2

Formula: a?n ? 1 (mod n)

The
equation a = b (mod n) means that n is a divisor of a – b. It is a remainder,
because if you subtract a remainder from the dividend, the divisor will go into
the result evenly.3

Eg:
100 = 86 (mod 7), because 100 – 86 = 14 has 7 as a divisor.

Here,
?n is Euler’s totient function, which
counts the number of positive integers ? n
which are relatively prime to n.4

For
example, ?10 is 4 as there are four number less than ten that are relatively
prime to 10 {1, 3, 7, 9}, and ?6 is 2 as 1 and 5 are relatively
prime to 6, but 2,3 and 4 are not. However,
?7 is 6, as 7 is a prime and all numbers less than it are relatively
prime to it. Attached below is a table of totients to the number 10 that I will
use for further examples.

Table.1-
totients for real numbers

n

?n

1

0

2

1

3

2

4

2

5

4

6

2

7

6

8

4

9

6

10

4

Solving
an example: Let n = 10 and a = 3. When taking an example both a and n need to be coprime otherwise the formula will not work and I
chose to take small values to easily demonstrate. From the table, we know ?10 =
4.

Then,
34 = 81 ?1(mod 10).

 

Fermat’s
little theorem

Suppose a is relatively prime to 10. By
referring to the table, you can see Euler’s theorem says that a4=1
(mod 10) showing that the last digit of a4 is always 1 which is the
summary of the example we solved. To fully prove Euler’s theorem, we need to
understand Fermat’s little theorem. Euler’s
totient theorem is a generalisation of Fermat’s little theorem and works for
all n relatively prime to a. Fermat’s little theorem only works for a and p
relatively prime where p is itself prime and states5:

ap ? a (mod p)

or

ap-1 ? 1 (mod
p)

You can see the
connection with Euler’s totient theorem for p, as we have seen ?p, where p is a
prime, is always p-1, for example ?7 which we solved to 6 (p-1).

 

Proving Euler’s totient
theorem through set theory and mod

Formula:
a?n ? 1 (mod n)

1)
Take two numbers, a and n, as shown above they have to be
relatively prime for the formula to work.

2)
Consider the set N of numbers that are relatively prime to n {1, n1, n2, n3, n4…}
We use these notations because we do not know the values.

3)
The set has to have ?n number of
elements, because it is the number relatively prime to it, as we solved in the
table.

4)
Consider the set aN, where each
element is the product of a and an
element of N { a, an1,an2, an3, an4…},
a can be any value but the set created has to be in congruence to the other because we multiplied it.

5)
Each element in set aN will be congruent to an element in set N (mod n), because
mod shows the relationship between the multiples and the factors as we
explained before.

Therefore
{a, x, an1, x an2 x …} ? {1, x, n1 x, n2
x, …} (mod n)

6)
By taking out a factor of a?n from the side

a?n
{ 1, x n1 ,x n2 x … } ? { 1 x n1 x n2
x … } (mod n)

This
is because of the original formula which was a?n ? 1 (mod n) so by dividing it we are left with equal mod
values.

7)
The next step is to cancel out the mod on one side by, we divide the entire
equation by the original { 1 x n1 x n2 x … } which is
valid as all elements are coprime since we removed a?n

Therefore,
a?n ? 1 (mod n)

 

Exploring
an application

One
of the easiest applications that I could see, which connects to what we have
done in class is using Euler’s theorem to find the last digit of a complicated
power. In class, when we have to solve for complex numbers like 3212
I usually depend on my calculator and have no idea how to solve it quickly and
effectively. By using the theorem, you can find the last digit of the power
which then can give you a quick estimate when solving it.

Suppose
the question is to solve 3342,, although this isn’t a large power I’m
simplifying it so we can depend on the value table that I created.

We
can simplify it by denoting it as ?(100)= 40

3340=
1 (mod 100)

Therefore,
3342 = 332 (mod 100) = 89

When
we solve 3342we get 5.9921886e+63

When
expanded fully the last two digits, we now know the last two digits are 89.

Conclusion

It
is very interesting to see its applications in terms of sequences and series
which could be explored further. It simplifies the geometric succession that
could take place in a series and could potentially be explored further to
simplify calculating the values in geometric series. This has allowed me to
apply knowledge from mathematics that I did not know was connected to each
other and has helped broaden my view of maths. I know that it is impossible to
prove the last two digits of a large power but it has been scientifically
proven, and looking at my smaller examples I know this to be true and took it
as an assumption in my application.

However, the
biggest lesson that I have understood from this was the importance of combining
concepts to simplify things. Using the skills, I had learnt in math, I was able
to apply it to a completely different real-world situation. This IA has left me
wondering how many other unexpected places I could begin to apply Euler’s theorem
to answer real, relevant questions in our society.

 

 

1 https://brilliant.org/wiki/eulers-theorem/

2 https://en.wikipedia.org/wiki/Coprime_integers

3 https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-quotient-remainder-theorem

4 https://en.wikipedia.org/wiki/Euler’s_theorem

5 https://en.wikipedia.org/wiki/Fermat%27s_little_theorem

Post Author: admin

x

Hi!
I'm Irvin!

Would you like to get a custom essay? How about receiving a customized one?

Check it out