PROFESSOR: Another way to talk about congruence and remainder
PROFESSOR: Another way to talk about congruence and remainder

arithmetic is to work strictly with remainders,
arithmetic is to work strictly with remainders,

which makes things a little simpler because you don't have
which makes things a little simpler because you don't have

to worry about the fact that the product of two remainders
to worry about the fact that the product of two remainders

may, for example, be too big to be a remainder.
may, for example, be too big to be a remainder.

To knock it back in range, you have
To knock it back in range, you have

to take the remainder again.
to take the remainder again.

And that's what this abstract idea
And that's what this abstract idea

of the ring of integers modulo n, the ring Z sub n,
of the ring of integers modulo n, the ring Z sub n,

captures in a quite elegant way.
captures in a quite elegant way.

So it's going to allow us to talk strictly about equality
So it's going to allow us to talk strictly about equality

instead of congruence.
instead of congruence.

And let's remind ourselves that the basic idea behind working
And let's remind ourselves that the basic idea behind working

with a remainder arithmetic was that every time we
with a remainder arithmetic was that every time we

got a number that was too big to be a remainder,
got a number that was too big to be a remainder,

we just hit it with the remainder operation
we just hit it with the remainder operation

again to bring it back in range.
again to bring it back in range.

And so the operations in Zn work exactly that way.
And so the operations in Zn work exactly that way.

The elements of Zn are the remainders.
The elements of Zn are the remainders.

That is, the numbers from 0, including 0, up to n,
That is, the numbers from 0, including 0, up to n,

but not including n.
but not including n.

So there are n of them from 0, 1, up through n minus 1.
So there are n of them from 0, 1, up through n minus 1.

And the definitions of the operations in Zn
And the definitions of the operations in Zn

are given right here.
are given right here.

Addition just means take this sum
Addition just means take this sum

but then take the remainder immediately,
but then take the remainder immediately,

just in case it's too big.
just in case it's too big.

And likewise, the product in Zn is simply multiply them
And likewise, the product in Zn is simply multiply them

and take the remainder.
and take the remainder.

This isn't really a very dramatic idea,
This isn't really a very dramatic idea,

but it turns out to pay off in making some things just
but it turns out to pay off in making some things just

a little bit easier to say, because we're
a little bit easier to say, because we're

talking about equality instead of congruence.
talking about equality instead of congruence.

So this package together, this mathematical structure
So this package together, this mathematical structure

consisting of the integers in this interval--
consisting of the integers in this interval--

remember this notation, square bracket
remember this notation, square bracket

means inclusive and round parenthesis means exclusive.
means inclusive and round parenthesis means exclusive.

So this includes zero, it doesn't include n.
So this includes zero, it doesn't include n.

The integers in that interval, under the operations
The integers in that interval, under the operations

of plus and times modulo Zn, as defined here,
of plus and times modulo Zn, as defined here,

is called the ring of integers Zn.
is called the ring of integers Zn.

So it's got two operations and a bunch
So it's got two operations and a bunch

of things that are operated on.
of things that are operated on.

Now I guess it's worth highlighting.
Now I guess it's worth highlighting.

That's what Zn is, the ring of integers.
That's what Zn is, the ring of integers.

Mod n, or modulo n.
Mod n, or modulo n.

Now, arithmetic in Zn is really just arithmetic-- congruence
Now, arithmetic in Zn is really just arithmetic-- congruence

arithmetic, except that it's equality now instead
arithmetic, except that it's equality now instead

of congruence.
of congruence.

So we can say, for example, in Z7 that 3 plus 6
So we can say, for example, in Z7 that 3 plus 6

is literally equal to 2 because, well, 3 plus 6 is 9,
is literally equal to 2 because, well, 3 plus 6 is 9,

the remainder on division by 7 is 2,
the remainder on division by 7 is 2,

and we go directly to the two in Zn,
and we go directly to the two in Zn,

suppressing the mention of taking remainders and not even
suppressing the mention of taking remainders and not even

really having to think about it, which is what's
really having to think about it, which is what's

helpful about working with Zn.
helpful about working with Zn.

Likewise, 9 times 8 is literally equal to 6 in Z11.
Likewise, 9 times 8 is literally equal to 6 in Z11.

So what's the connection between the set of all the integers
So what's the connection between the set of all the integers

and the integers mod n?
and the integers mod n?

And we can state this abstractly in the following way.
And we can state this abstractly in the following way.

Let's just, for convenience, abbreviate the remainder of k
Let's just, for convenience, abbreviate the remainder of k

on division by n as R of k.
on division by n as R of k.

So n is fixed.
So n is fixed.

And what's the connection between Z and Zn?
And what's the connection between Z and Zn?

Well, it's fairly simple.
Well, it's fairly simple.

If you take the remainder of i plus j,
If you take the remainder of i plus j,

that's literally equal to taking the sum
that's literally equal to taking the sum

of the remainders in Zn.
of the remainders in Zn.

Once you've taken the remainders,
Once you've taken the remainders,

you're in the range of numbers that Zn works with.
you're in the range of numbers that Zn works with.

And this sum, then, keeps you in on the Zn side.
And this sum, then, keeps you in on the Zn side.

Likewise, if you take the remainder
Likewise, if you take the remainder

of a product of real integers, that's
of a product of real integers, that's

literally equal to the product of the remainders in Zn.
literally equal to the product of the remainders in Zn.

This operation, by the way, this connection
This operation, by the way, this connection

between mathematical structures, the structure
between mathematical structures, the structure

of the integers under plus and times
of the integers under plus and times

and Zn under plus and times, is called a homomorphism.
and Zn under plus and times, is called a homomorphism.

R, in this case, is defining a homomorphism from Z to Zn.
R, in this case, is defining a homomorphism from Z to Zn.

That's a basic concept in algebra
That's a basic concept in algebra

that you'll learn more about if you
that you'll learn more about if you

take some courses in algebra, but I'm just mentioning it
take some courses in algebra, but I'm just mentioning it

for cultural reasons.
for cultural reasons.

We're not going to exploit it any further,
We're not going to exploit it any further,

or look further into this idea.
or look further into this idea.

OK.
OK.

What's the connection between equivalence mod
What's the connection between equivalence mod

n, or congruence mod n, and Zn?
n, or congruence mod n, and Zn?

Well, it's fairly simple.
Well, it's fairly simple.

In Zn, we convert congruences into equalities.
In Zn, we convert congruences into equalities.

So i is congruent to j mod n if and only if r of i
So i is congruent to j mod n if and only if r of i

is equal to r of j in Zn.
is equal to r of j in Zn.

And this is just a rephrasing of the fact
And this is just a rephrasing of the fact

that two numbers are congruent if
that two numbers are congruent if

and only if they have the same remainder.
and only if they have the same remainder.

Now once you've got this self-contained system Zn,
Now once you've got this self-contained system Zn,

you can start talking about algebraic rules
you can start talking about algebraic rules

that it satisfies.
that it satisfies.

And now, they hold with equality and they're pretty familiar.
And now, they hold with equality and they're pretty familiar.

So let's look at some of the rules for addition,
So let's look at some of the rules for addition,

for example, that hold true in Zn.
for example, that hold true in Zn.

First of all, addition is associative.
First of all, addition is associative.

i plus j plus k is i plus j plus k.
i plus j plus k is i plus j plus k.

We have an identity element, literally zero.
We have an identity element, literally zero.

Zero plus any i is i.
Zero plus any i is i.

We have a minus operation, an inverse operation, with respect
We have a minus operation, an inverse operation, with respect

to addition, which is that-- how do I get back some slides?
to addition, which is that-- how do I get back some slides?

Excuse me.
Excuse me.

OK, let's keep going.
OK, let's keep going.

I have an inverse operation, which is that for every i,
I have an inverse operation, which is that for every i,

there's an element called minus i.
there's an element called minus i.

It's additive inverse such that if you add i and minus i,
It's additive inverse such that if you add i and minus i,

you get zero.
you get zero.

And finally, commutativity, which
And finally, commutativity, which

is that i plus j is the same as j plus i.
is that i plus j is the same as j plus i.

You don't really need to memorize these names,
You don't really need to memorize these names,

but you will probably hear them a lot
but you will probably hear them a lot

in various other contexts, and especially in algebra courses,
in various other contexts, and especially in algebra courses,

but even in terms of arithmetic.
but even in terms of arithmetic.

These are some of the basic rules that addition satisfies.
These are some of the basic rules that addition satisfies.

And in fact, multiplication satisfies
And in fact, multiplication satisfies

pretty much the same rules.
pretty much the same rules.

Multiplication is likewise associative.
Multiplication is likewise associative.

There's an identity for multiplication called 1.
There's an identity for multiplication called 1.

1 times i is i.
1 times i is i.

Multiplication is also commutative.
Multiplication is also commutative.

The one obvious omission here is inverses.
The one obvious omission here is inverses.

You can't count on there being inverses in Zn.
You can't count on there being inverses in Zn.

And finally, there's an operation
And finally, there's an operation

that connects addition and multiplication called
that connects addition and multiplication called

distributivity.
distributivity.

Namely, i times j plus k is ij plus ik,
Namely, i times j plus k is ij plus ik,

as you well know from ordinary arithmetic.
as you well know from ordinary arithmetic.

And this rule works fine for remainders and working in Zn.
And this rule works fine for remainders and working in Zn.

As I said, the one thing we have to watch out
As I said, the one thing we have to watch out

for, it shouldn't be a surprise, is we
for, it shouldn't be a surprise, is we

know that you can't cancel with respect to congruence mod n.
know that you can't cancel with respect to congruence mod n.

And that's reflected in the fact that you can't cancel in Zn.
And that's reflected in the fact that you can't cancel in Zn.

Namely, in Z12, for example, 3 times 2 is equal to 2 times 8.
Namely, in Z12, for example, 3 times 2 is equal to 2 times 8.

Again, 3 times 2 is 6, 2 times 8 is 16,
Again, 3 times 2 is 6, 2 times 8 is 16,

you immediately take the remainder to get back to 6.
you immediately take the remainder to get back to 6.

In Z12, these two things are equal.
In Z12, these two things are equal.

But if you tried to cancel the 2, you'd conclude that 3 was 8,
But if you tried to cancel the 2, you'd conclude that 3 was 8,

and neither 3-- 3 and 8 are different numbers
and neither 3-- 3 and 8 are different numbers

in the range from 0 to 12, and they're different in Z12.
in the range from 0 to 12, and they're different in Z12.

So you can't cancel 2.
So you can't cancel 2.

OK.
OK.

Now the rules that we already figured out
Now the rules that we already figured out

for when you can cancel in congruence
for when you can cancel in congruence

translate directly over to when you can cancel in Zn.
translate directly over to when you can cancel in Zn.

And now there's a standard abbreviation
And now there's a standard abbreviation

that's useful to use here.
that's useful to use here.

If I write Zn*, what I mean is the elements in Zn that are
If I write Zn*, what I mean is the elements in Zn that are

relatively prime to n.
relatively prime to n.

The elements whose GCD with n is 1.
The elements whose GCD with n is 1.

So what we have is the following equivalent formulations of Zn*,
So what we have is the following equivalent formulations of Zn*,

which correspond to the facts we've already figured out about
which correspond to the facts we've already figured out about

congruence.
congruence.

Namely, an integer i in the range from 0 to n is in Zn*
Namely, an integer i in the range from 0 to n is in Zn*

if and only if the GCD of i and n is 1,
if and only if the GCD of i and n is 1,

or i is cancelable in Zn, or i has an inverse in Zn.
or i is cancelable in Zn, or i has an inverse in Zn.

All of these three things are equivalent.
All of these three things are equivalent.

They give you the sense that Zn* is a kind of robust subset
They give you the sense that Zn* is a kind of robust subset

of Zn that you'd want to be thinking about.
of Zn that you'd want to be thinking about.

And in fact, it's very valuable to be paying attention to.
And in fact, it's very valuable to be paying attention to.

What else do we know about Zn*?
What else do we know about Zn*?

Well, the definition of phi of n was the number
Well, the definition of phi of n was the number

of integers in the interval from 0
of integers in the interval from 0

to n that are relatively prime to n.
to n that are relatively prime to n.

Of course, that's exactly the size of Zn*.
Of course, that's exactly the size of Zn*.

So phi of n is simply the size of that collection of elements.
So phi of n is simply the size of that collection of elements.

Not surprising.
Not surprising.

They were defined that way.
They were defined that way.

So now I can restate Euler's Theorem
So now I can restate Euler's Theorem

in a slightly convenient way.
in a slightly convenient way.

Instead of mentioning congruence,
Instead of mentioning congruence,

we can just talk about equality.
we can just talk about equality.

Euler's Theorem says that if you raise a number k to the power
Euler's Theorem says that if you raise a number k to the power

phi of n, it's literally equal to 1 in Zn,
phi of n, it's literally equal to 1 in Zn,

at least for those k's that are relatively prime to n.
at least for those k's that are relatively prime to n.

That is, those k's that are in Zn*.
That is, those k's that are in Zn*.

And it's going to turn out that the proof of Euler's Theorem
And it's going to turn out that the proof of Euler's Theorem

is actually pretty easy.
is actually pretty easy.

It just follows in a couple of steps
It just follows in a couple of steps

from a couple of simple observations.
from a couple of simple observations.

So let's start on those.
So let's start on those.

So the first remark is that if I have any subset, S, of elements
So the first remark is that if I have any subset, S, of elements

in Zn-- I don't care whether they are relatively prime to n
in Zn-- I don't care whether they are relatively prime to n

or not-- if I multiply each of them by k,
or not-- if I multiply each of them by k,

this notation for k times S means
this notation for k times S means

that I'm taking the set of elements that are of the form
that I'm taking the set of elements that are of the form

k times an element of S over all the elements of S.
k times an element of S over all the elements of S.

So kS, which is this set of multiples
So kS, which is this set of multiples

of k-- multiples of elements of S by k,
of k-- multiples of elements of S by k,

has exactly the same size as S.
has exactly the same size as S.

Now, why is that?
Now, why is that?

Well, this of course is only true for k that are cancelable.
Well, this of course is only true for k that are cancelable.

But the Lemma is, no matter what subset you take of Zn,
But the Lemma is, no matter what subset you take of Zn,

if you multiplied every one of them by an element
if you multiplied every one of them by an element

that's cancelable in Zn*, you get a set of the same size.
that's cancelable in Zn*, you get a set of the same size.

And that's clear because how could ks1 and ks2 be equal?
And that's clear because how could ks1 and ks2 be equal?

Well, only if s1 and s2 were equal.
Well, only if s1 and s2 were equal.

Or another way to say it is that if you
Or another way to say it is that if you

had different elements in S, s1 not equal to s2,
had different elements in S, s1 not equal to s2,

when you multiply them by k, you have
when you multiply them by k, you have

to get different elements of ks, because k is cancelable.
to get different elements of ks, because k is cancelable.

OK.
OK.

So that's an easy remark.
So that's an easy remark.

Holds in general.
Holds in general.

Multiply any subset by a cancelable element,
Multiply any subset by a cancelable element,

and you get a new set that's the same size.
and you get a new set that's the same size.

The second remark is that if you look at numbers i and j that
The second remark is that if you look at numbers i and j that

are in the interval from 0 to n in Zn,
are in the interval from 0 to n in Zn,

then if you multiply the two of them,
then if you multiply the two of them,

then you're going to get an element in Zn* if and only
then you're going to get an element in Zn* if and only

if the original two elements were in Zn*.
if the original two elements were in Zn*.

Well, let's just look at it in the left to right direction,
Well, let's just look at it in the left to right direction,

which is the only one we need.
which is the only one we need.

If i and j are relatively prime to Zn*,
If i and j are relatively prime to Zn*,

then so is their product, because if neither i nor j has
then so is their product, because if neither i nor j has

a prime factor in common with n, then their product obviously
a prime factor in common with n, then their product obviously

doesn't have a factor in common with n.
doesn't have a factor in common with n.

And then when you take remainders,
And then when you take remainders,

it's still going to be a number whose GCD is the same.
it's still going to be a number whose GCD is the same.

And so we have this remark that if you
And so we have this remark that if you

multiply two cancelable elements,
multiply two cancelable elements,

you get a cancelable element.
you get a cancelable element.

If you multiply two elements relatively prime to Zn*,
If you multiply two elements relatively prime to Zn*,

you get an element of Zn*.
you get an element of Zn*.

There's about-- every one of these formulations of Zn*
There's about-- every one of these formulations of Zn*

in terms of GCDs are cancelable or inverse,
in terms of GCDs are cancelable or inverse,

and each of them gives a separate and straightforward
and each of them gives a separate and straightforward

proof of the fact that if i and j are in Zn*,
proof of the fact that if i and j are in Zn*,

then so is their product.
then so is their product.

Now it's worth mentioning, by the way,
Now it's worth mentioning, by the way,

that, in general, their sum is not.
that, in general, their sum is not.

If you add two elements that are relatively prime to Zn*,
If you add two elements that are relatively prime to Zn*,

even if their sum is non-zero, you will typically get
even if their sum is non-zero, you will typically get

an element that is no longer relatively prime to n.
an element that is no longer relatively prime to n.

But for multiplication, it works great,
But for multiplication, it works great,

and that's what matters to us.
and that's what matters to us.

OK.
OK.

So as a corollary of this is that I can actually conclude
So as a corollary of this is that I can actually conclude

that, if I choose an element that's cancelable,
that, if I choose an element that's cancelable,

an element in Zn*, if I take the whole set Zn*,
an element in Zn*, if I take the whole set Zn*,

all those elements that are relatively prime to n,
all those elements that are relatively prime to n,

and I take multiples of k by each of them, then, in fact,
and I take multiples of k by each of them, then, in fact,

I get the same set, Zn*.
I get the same set, Zn*.

And the proof of that is really straightforward.
And the proof of that is really straightforward.

Let's think about it for a minute.
Let's think about it for a minute.

Because what do I know is that these two sets
Because what do I know is that these two sets

are the same size.
are the same size.

kZn* and Zn* are the same size.
kZn* and Zn* are the same size.

As long as k is cancelable, I don't even care that this was
As long as k is cancelable, I don't even care that this was

Zn*.
Zn*.

On the other hand, if k is in Zn*,
On the other hand, if k is in Zn*,

k times Zn* only gives you elements in Zn*.
k times Zn* only gives you elements in Zn*.

So kZn* is a subset of the left-hand side,
So kZn* is a subset of the left-hand side,

and it's the same size by the Lemma that says that
and it's the same size by the Lemma that says that

multiplying by k preserves sizes.
multiplying by k preserves sizes.

So they have to be equal.
So they have to be equal.

So basically what that means is that if you take all
So basically what that means is that if you take all

the elements in Z*, all the elements relatively prime to n,
the elements in Z*, all the elements relatively prime to n,

and you take another one of them, pick one out of that set,
and you take another one of them, pick one out of that set,

and multiply every element in the set by that element k,
and multiply every element in the set by that element k,

if you had them lined up in one order beforehand,
if you had them lined up in one order beforehand,

when you multiplied by k you get exactly the same elements
when you multiplied by k you get exactly the same elements

but just reordered.
but just reordered.

That is, multiplying by k has the effect of permuting
That is, multiplying by k has the effect of permuting

the elements of Zn*.
the elements of Zn*.

Let's look at an example.
Let's look at an example.

So let's look at Z9.
So let's look at Z9.

And we know that phi of 9, by the previous formula,
And we know that phi of 9, by the previous formula,

is 3 squared minus 3, or 6.
is 3 squared minus 3, or 6.

There are going to be 6 elements from 0 to n that are relatively
There are going to be 6 elements from 0 to n that are relatively

prime to 9, and that comprise Zn*.
prime to 9, and that comprise Zn*.

So let's look at what they are.
So let's look at what they are.

So you can do-- check the calculation.
So you can do-- check the calculation.

But Zn* is exactly the elements 1, 2, 4, 5, 7, 8.
But Zn* is exactly the elements 1, 2, 4, 5, 7, 8.

We know we got them all because there's only
We know we got them all because there's only

supposed to be six of them, and we
supposed to be six of them, and we

can check that those are all relatively prime to 9.
can check that those are all relatively prime to 9.

None of them has 3 as a divisor.
None of them has 3 as a divisor.

Now what happens, for example, if I multiply them all by 2?
Now what happens, for example, if I multiply them all by 2?

Two is another good number-- it's right here--
Two is another good number-- it's right here--

that's in Zn*.
that's in Zn*.

And multiplying them by 2, well, let's check.
And multiplying them by 2, well, let's check.

2 times 1 is 2, 2 times 2 is 4, 2 times 4 is 8,
2 times 1 is 2, 2 times 2 is 4, 2 times 4 is 8,

2 times 5 is 1-- because it's 10 with a remainder of 1-- 2 times
2 times 5 is 1-- because it's 10 with a remainder of 1-- 2 times

7 is 14-- translates into 5-- 2 times 8
7 is 14-- translates into 5-- 2 times 8

is 16-- [INAUDIBLE] translates into 7.
is 16-- [INAUDIBLE] translates into 7.

And, as claimed, look at this.
And, as claimed, look at this.

Here's 2, 4, 8, 1, 5, 7.
Here's 2, 4, 8, 1, 5, 7.

It's the same numbers as 1, 2, 4, 5, 7, 8,
It's the same numbers as 1, 2, 4, 5, 7, 8,

just in a different order.
just in a different order.

Let's do one more example.
Let's do one more example.

Let's try multiplying by 7.
Let's try multiplying by 7.

That's another respectable element over here.
That's another respectable element over here.

7 times 1 is 7, 7 times 2 is 14, which means it's 5 in Z9.
7 times 1 is 7, 7 times 2 is 14, which means it's 5 in Z9.

4 times 7 is 28.
4 times 7 is 28.

Well, 3 times 7 is 27, so that leaves a remainder of 1.
Well, 3 times 7 is 27, so that leaves a remainder of 1.

And 4 times 7 is 1 in Z9.
And 4 times 7 is 1 in Z9.

Likewise, 5 times 7 is 8, 7 times 7 is 4, and 7 times 8
Likewise, 5 times 7 is 8, 7 times 7 is 4, and 7 times 8

is 56, which translates to 2.
is 56, which translates to 2.

And sure enough, as claimed, I see the same numbers, 7, 5, 1,
And sure enough, as claimed, I see the same numbers, 7, 5, 1,

8, 4, 2, just these numbers scrambled in order.
8, 4, 2, just these numbers scrambled in order.

They're permuted, which is the outcome of multiplying by 7.
They're permuted, which is the outcome of multiplying by 7.

OK.
OK.

So let's go back.
So let's go back.

What we've just illustrated is this fact that we've already
What we've just illustrated is this fact that we've already

concluded that, if you take Zn* and you multiply it
concluded that, if you take Zn* and you multiply it

by an element k in Zn*, you get the same set in a different
by an element k in Zn*, you get the same set in a different

order.
order.

So Zn* is equal to k times Zn*.
So Zn* is equal to k times Zn*.

And now we're on the brink of proving Euler's Theorem.
And now we're on the brink of proving Euler's Theorem.

Because what I want to do is say, look,
Because what I want to do is say, look,

these two sets are the same.
these two sets are the same.

Let's multiply all the elements on the left
Let's multiply all the elements on the left

together, and multiply all the elements on the right together.
together, and multiply all the elements on the right together.

Let's take the product of those elements.
Let's take the product of those elements.

So let's take the product of Zn* and compare it to the product
So let's take the product of Zn* and compare it to the product

of kZn*.
of kZn*.

So big pi here is indicating the product
So big pi here is indicating the product

of all of the elements in this set, the product of all
of all of the elements in this set, the product of all

of the elements in this set.
of the elements in this set.

Well, let's look at the set on the right.
Well, let's look at the set on the right.

This is the product of k times all the elements in Z*.
This is the product of k times all the elements in Z*.

Well how many elements are there?
Well how many elements are there?

Phi of n elements in Z*, by definition.
Phi of n elements in Z*, by definition.

And let's factor out all the k's.
And let's factor out all the k's.

So this expression here, the product of k times each element
So this expression here, the product of k times each element

in Zn*, is the same as the product of the elements in Zn*
in Zn*, is the same as the product of the elements in Zn*

times k to as many elements as there were,
times k to as many elements as there were,

namely k to the phi of n.
namely k to the phi of n.

I'm just factoring k out of this product.
I'm just factoring k out of this product.

And there's my k to the phi of n.
And there's my k to the phi of n.

And now look what I got here.
And now look what I got here.

That's pi Zn*, and that's pi Zn*.
That's pi Zn*, and that's pi Zn*.

What do I know about multiplying elements in Zn*?
What do I know about multiplying elements in Zn*?

They're in Zn*.
They're in Zn*.

This product will be some other element is Zn*.
This product will be some other element is Zn*.

So will this product.
So will this product.

But what do I know about Zn*?
But what do I know about Zn*?

They're cancelable.
They're cancelable.

So just looking-- ignoring the middle term now,
So just looking-- ignoring the middle term now,

what I'm concluding is that the product of Zn* is k to the phi
what I'm concluding is that the product of Zn* is k to the phi

of n times the product of Zn*.
of n times the product of Zn*.

Let's cancel those cancelable terms.
Let's cancel those cancelable terms.

And I'm done.
And I'm done.

I've just figured out that 1, which
I've just figured out that 1, which

is the result of canceling the term on the left,
is the result of canceling the term on the left,

is equal to k to the phi of n.
is equal to k to the phi of n.

And we have successfully proved Euler's Theorem,
And we have successfully proved Euler's Theorem,

which is what we were aiming for in this segment.
which is what we were aiming for in this segment.