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.

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