Introduction to Number Theory - Cryptography & Network Security Video Lecture - Computer Science Engineering (CSE)

so welcome to this talk our lecture on
number theory so today we shall be
discussing about some elementary
concepts in number theory which forms
the kind of PI Center I mean it is very
central to the field of Technology so we
shall it's a really fascinating field
and quite a big vast field but today we
shall essentially understand some of the
basic concepts
so today's objective of this particular
talk shall be on congruence is modular
arithmetic introduction to field theory
all our totient function and formats
little theorem so we shall be talking
about these topics so one of them is
congruences which is modular arithmetic
which is very important to understand
the field of cryptology and then we
shall try to give the define the concept
of what is meant by a mathematical field
which is very again very a central idea
to study and then discuss about a
particular function which is called as
euler totient function and very popular
and very useful kind of parameter and
then conclude the talk with our
discussion on format still two theorems
we will be actually discussing about
format euler's theorem
so starting so essentially you will find
that when we are doing cryptology or
when we are doing a normal kind of
computation I mean in relate to the
ciphers then we essentially do not deal
with in finite sequences okay so we for
example will not have a set which are
rather we do not have a set which is
which can be which can take infinitely
large number of values so which means
that there is a finite number of values
and we are supposed to do our
computations on finite values so so
therefore there is I mean we have to
define our arithmetic in a finite set of
values so for that or rather in order to
study such kind of operations one basic
concept or one very important concept is
something which is called as congruences
so we say that a is congruent to b
modulo m so a and we are supposed to
integral integer numbers and we say that
a is congruent to b modulo m
and we denote them as follows that is a
is congruent to B mod M if M divides a
minus B or B minus a so that is the
basic idea so let let us see some
examples like -2 will be is equal to
will be congruent to 19 modulo 21 reason
being that 21 divides 19 minus of minus
2 that is 21 and similarly 20 will be 0
mod 10 because if we take rather one way
of thinking is that 10 will divide 20
minus 0 or 0 minus 20 so I mean so
therefore I mean the idea is that if you
just think in terms of numbers then this
number if we divide by the modulus of
operation and then this particular
number on the right hand side is nothing
but the remainder so therefore so that
is a way of how to kind of compute a
modular calculation so this is nothing
but the simple modulo computation now he
noted that congruence modulo M is
actually an equivalence relation why
because it is an equivalence relation on
the set of integers okay so let us try
to reason it out so we know that for in
order for a particular relation to be
satisfying the properties of any key
balance relation it has to satisfy three
important concepts of reflexivity
symmetricity and also transitivity so
let us try to first of all argue why
it's reflexive okay so we see that
reflexive it is reflexive because any
integer is congruent to itself modulo M
so therefore if you take a number a or
rather you just take any number then
this number is also congruent to itself
okay so why is because of this that is
if you take a number a and discuss that
whether and I say that is kind of a is
congruent to a mod M right so therefore
this is perfectly okay why now because
this means that M divides a minus a
which is zero okay so this is true so
therefore a is congruent to a modulo M
so therefore the reflexive 'ti
relationship holds okay so therefore if
I define my relay
by congruence which means that a number
a is related to B if a is congruent to B
modulo M this is the basic definition of
the of the relation that we are
considering of the congruence relation
then this relation satisfies the
property of reflexivity because of this
reason
now what about symmetricity now you see
that in terms of symmetricity also it
holds because as we say that if a is
congruent to b modulo m then it also
holds that b is congruent to a modulo m
why now because this says that if m
divides a minus b then m also divides b
minus a ok so therefore the symmetric
symmetric c relation also holds and this
is true for all all a and B ok so there
it is true for all integer values a and
B now this is very important okay that
is it holds for this relation holds the
symmetricity property holds for all
values of a and B what about
transitivity so you see that in it is
also transitive why not because if a is
related to B mod M okay and I tell you
that B is congruent to C mod M okay then
this implies that a is congruent to C
mod M okay why and because you see that
M divides a minus B okay and M divides B
minus C okay so from there we can
conclude the name also divides a minus C
why and because you could have written
this a minus B more simply as some
multiple of M similarly you could have
written B minus C as some other multiple
of M okay so now if you have added these
two equations right if
simply added these two equations then
you would have got a minus B plus B
minus C is nothing but lambda plus mu
which is again another integer times M
so now from here B & B cancels and you
have got a minus C is equal to some
other constant you can call that to say
V some epsilon or something or so it's
something some integer multiplied with M
and therefore this means that M divides
a minus C and therefore this this also
holds true okay so we see that this
relation is also transitive and
therefore since it is and this will hold
for any such a B and C right and
therefore since it satisfies the
properties of reflexivity symmetricity
and also of transitivity we say that
this particular relation of congruence
also satisfies the process I mean it's
an equivalence relation okay so
therefore it basically induces a
partition on the set of integers okay we
know that equivalence relation induces a
set of party I mean induces a set
induces a partition on the set on the
set right so therefore it this property
holds true now the following are
actually some equivalent statements and
you can easily verify them it says that
a is congruent to B mod M is same as
saying that there is an integer value of
K which satisfies that a is equal to B
plus K M so this is what I just just
wrote in the previous slide okay so you
see that M divides a minus B because a
minus B is K because an integer
multiplied with M fits it's an integral
multiple of M now when divided by M then
both a and B leave the same remainder so
this is also its same as saying as a is
congruent to be modular em now
equivalence class of a model of a modulo
M that is a modulo M consists of all
integers that are obtained by adding a
with integral multiples of M now this is
called or define as the residue class of
a mod M okay so which means that if I
say that there is a class which is
called a residue class of a mod M then
what we do is that we take a and we add
all possible integral multiples of M
okay so
so therefore if I say you that there is
a residue class of there is a residue
class of a mod M then it means that this
consists of all integers okay so it is
basically a set of all integers which
are obtained by adding a with integer
multiples of of M so therefore it could
be like a plus minus M a plus minus 2m
and so on okay so the basic idea is that
if you just take any number out from
here and if you divide it by m then the
remainder which you obtain is a okay so
therefore the remainder defines that
particular class okay so therefore this
class is a residue class of a mod M and
it is also an equivalence class because
it satisfies the I mean it's on you it
satisfies the properties of equivalence
we have just seen that right so so
therefore so here is an example for a
residue class of 1 modulo 4 so 1 modulo
4 will be 1 and then 1 plus minus 4 so
therefore again 1 plus minus 2
multiplied by 4 and then 1 plus -3
multiple of multiplied by 4 and so on so
the set of residue class is mod M is
denoted by Z MZ so that this is also
noted in this in this fashion so this
particular notation is also sometimes
known as them okay it is also denoted as
Z I mean you can also denote it as like
this okay so it is also an equivalent
way of maybe a shorter way of
representing this set okay so this this
just defines that this is the set of
residue classes mod M okay and it is
denoted by Z / NZ and that is equal to Z
M so therefore now now this particular
set okay we will have all the possible
all the possible values so it will
essentially have M values okay so what
are the M values possible name values
will run from 0 1 until M minus 1 okay
so this is a set which essentially
comprises of these values that is
0 to M minus 1 now this is also called
an a complete system or a complete set
of incongruent residues okay so
therefore you see that if you just take
a number so an example of this would be
like let us take the example of ten okay
and then define like what is Z by ten Z
okay so then this will comprise of
numbers from 0 1 till in till line okay
that is 10 minus 1 is 9 so that means
that if you just take M is equal to 10
then these are the possible values of
numbers okay which are which are
possible I mean which are maximally
possible and which also have which are
also incongruent to each other so that
means that if you take any numbers from
this from this set for example let us
take like one example one random choice
could be like two and another arbitrary
choice could be say 5 then 2 & 5 are
never congruent to each other modulo 10
okay so that is why Y is 2 not congruent
to 5 modulo 10 because 10 will not
divide to minus 5 or 5 minus 2 okay so
that means all the elements in this set
are actually incongruent to each other
and this is the maximal possible or
possible number of number of incongruent
values that can that can happen okay you
can take any number outside this
particular set for example if you just
take an arbitrary choice like say 12
then you will find one number in this
set okay which is congruent to this
number modulo 10 okay which is that
number for example you can choose two
okay so you see the two and twelve are
congruent to each other modulo ten why
because 10 will divide 12 minus two
right so therefore you will find that
this particular set which is like Z
defined by z slash MZ is also called a
complete set of incongruent residues or
a complete system now there are examples
this is an example given here for
complete system for modulo five so we
know for mod five it will be like from 0
to 5 minus 1 that is 0 1 10 4 and this
is another example you can verify like
this is minus 12 minus 1582 and minus 1
and 32 this
is also a complete system why now this
is also a complete system because if you
just take these numbers like you take
minus 12 okay so what you are
considering is Z / 5 Z right so you see
that in this set if you just take 12
then 12 is actually so it is minus 12
right so minus 12 if you take modulo 5
so what does it mean what is this value
so if you divide 12 by 5 okay so
therefore you will get that this is
equal to is it correct yes because if
you just take this number 5 okay then 5
will divide minus 12 plus 2 because that
is minus 12 plus 2 is nothing but minus
10 so 5 divides minus 10 okay now what
is - - if you if we would like to bring
it in this among these numbers like from
0 1 till 3 4 & 4 then this particular
number minus 2 will be actually equal to
3 okay so therefore because it is you
can verify this because 5 will again
divide minus 2 minus 3 okay so this is
the same as minus 2 modulo 5 will be
same as 3 modulo 5 what about the next
number the next number here in this set
was given as minus 15 okay so minus 15
if you take modulo 5 what will be it it
will be 0 okay so similarly you can do
it for the other ones also like 82 will
be equal to 2 modulo 5 because 5 will
divide it it to minus 2 and minus 1 will
be congruent to 4 mod 5 and 31 will be
congruent to 1 mod 4 1 1 1 5 so you see
that the numbers that I obtain after
taking the modulo 5 essentially are
nothing but another order of the numbers
0 1 2 3 & 4
so therefore
you see that this is also a kind of
these numbers like this set like - 12 -
15 82 minus 1 and 31 is also another
example of a complete system I am any
two numbers from this said okay are are
are are incongruent to each other they
are not congruent okay you can check
this so there is a theorem I mean I'm
really not I'm really not going to the
proof but it's very simple you can
verify it like if a is congruent to B
modulo N and C is congruent to D modulo
M then this implies that minus a and
minus B are congruent to each other
modulo M you can also add like a plus cz
congruent to B plus D modulo M there
should be a model M here and AC is
congruent to DD modulo M okay so you can
verify this and it's very simple like
what you can do is that you can start
like writing as a is equal to B plus
some constant multiple of Lumbee of m
and c is equal to d plus some constant
times m and then try to find out - a and
then C and this is very simple so this
is this is quite trivial to prove now
what is the implication of this result
now this there is a very strong
implication of this result okay so let
me reflect on this see for example what
we understand here is that this number a
may be quite a large value and this
number C may be also another quite large
value okay and suppose you are actually
interested in computing doing
computation and large values now if you
would like to do a computation of large
values but you always have this modular
m then the idea is that what it says is
that instead of taking a plus C or
rather adding a plus C and then doing a
modulo n is same as doing a modulo M on
a doing a modulo M on C and reducing
these numbers between 0 to M minus 1 and
then adding these two numbers ok so let
me kind of illustrate this with an
aviary simple example so let us take a
large value of a ok so for example
consider that a is up say again let us
consider that our M value is
five and let us see that a is suppose a
large value like maybe larger than this
so it may be like twenty seven okay and
let us consider another value which is
say B or rather C and consider that this
is say something like forty nine so now
let us try to add these two numbers so
we know that if we add these two numbers
then we get 76 and therefore if I do a
modulo five here that means that I
divide this by five and my remainder is
one okay so therefore I write that a
plus C okay modulo M is nothing but
equal to 1 is congruent to one so
another way of writing this is rather
the way we were writing is a plus C is
equal to 1 mod M okay so now let us try
to do I mean apply the previous result
so what we will do is that we will take
27 and perform a modulo 5 operation so
if I do that then I see that 25 is
divisible by 5 so the remainder is 2
similarly I take 49 and do a modulo 5
operation so we see that 45 is divisible
so this is actually equal to 4 okay so
now you see that 4 also can be written
as minus 1 right so so therefore we
write that 27 is equal to 2 mod 5 and 49
is minus 1 mod 5 so now if I add these
two numbers like 27 plus 49 then I can
opt a add this instead of adding these
two numbers and reducing what I can do
is that I can actually add these two
small numbers and I get 1 modulo 5 which
matches with this result so which means
that I need not do the additions with
large numbers when I am doing a modular
operation right when then I really do
not need to add these large numbers but
what I can do is that I can reduce these
numbers modulo 5 reduce this number
modulo 5 and then add these two numbers
so this particular particular technique
can actually make our computations quite
simple and
this is actually applied in the
implementation of cryptosystems quite
regularly to make your implementations
easier okay
so we will probably get this idea or
rather find more examples of this as we
proceed but this is a very interesting
and very important results which we
should understand similarly when we are
talking about multiplication we can also
again instead of multiplying two large
numbers which is even more complicated
we can actually reduce these numbers mod
M and then just multiply the small
numbers for example imagine like if you
have to multiply 27 and 49 and then do a
modulo 5 operation right then this book
this multiplication is not I mean it is
not so simple how to do it and you can
make mistakes right and most importantly
when a computer does it it may not make
mistakes but what it may do is that you
may require large number of time right
so the resource may be useful may be
used up so instead of that what you can
do is that you can reduce it it becomes
2 M it becomes minus 1 and you know that
this result is very simple this result
is starting nothing but minus 2 mod 5
which is nothing but 3 ok so you can
just straight away from these two
results you can obtain this product that
actually makes your computations much
easier otherwise you would have become a
little bit more difficult right so this
result has got lot of impact and
therefore and here is another example so
you can probably try to understand the
impact of the previous result from this
example so let us consider so this is
the very important number in number
theory but let us not go into that it
says that 2 to the power of 2 to the
power of 5 plus 1 is divisible by 6 41
and a proof is required for that so one
way of doing it like it will be 2 to the
power of 5 is 32 so the vapour let's
compute 2 to the power of 32 and then
add one and then divide by 641 and then
see that whether it is divisible or not
but this is a quite tedious approach
instead of that let us see these we note
that 641 can be actually written as 640
plus 1 and 640 can be factorized as 5
multiplied by 2 to the power of 7 plus 1
now this factorization is quite easy
right because it is divisible by 5 and
the others are just powers of 2 so now
therefore we can write as 5 multiplied
by 2 to the power of 7 is nothing but
minus 1 modulo 6
or t1 Y and because we know that v ^ ^ 7
will be equal to 641 minus 1 right so we
can rearrange this as 5 into 2 to the
power of 7 is equal to 641 minus 1 now
if I take a modulo six forty one then
this vanishes and therefore minus one
remains of the demander so now from the
previous result we know that if I raise
this to the left hand side to the power
of 4 it's same as right I mean raising
the right hand side to the power of
minus 1 whole to the power of 4 when we
are doing modulo six forty one operation
because this means that we are
multiplying this four times and
therefore the right hand side also needs
to be multiplied 4 times so therefore
straight away from here we get 5 to the
power of 4 multiplied by 2 power of 28
is nothing but congruent to 1 modulo six
forty one so now we see that 5 to the
power of 4 is nothing but 6 20 fun as
625 and we know that we need not
actually require to multiply these two
numbers but we can actually reduce this
number modulo six forty one so that
should make our computations easy right
and then multiply it by 2 power 28 and
that is congruent to 1 modulo six forty
one so this equation is not disturbed by
this so now we see that 625 modulo six
forty one is nothing but equal to -16 so
therefore this result is nothing but
minus 2 power of 4 multiplied by 2 power
of 28 is congruent to 1 modulo six forty
one and that means that 2 power of 32 is
nothing but equal to minus 1 modulo six
forty one so that means that 641 divides
from the definition of congruence we
know 641 divides to power of 32 minus or
minus 1 that is 641 divides to power of
32 plus one so this particular thing is
proved but you see that throughout this
we are actually not done a single big
large computation and that is advantage
of the previous theorem okay so
therefore the idea is that when you need
to do multiplications or additions or
computations on large numbers and when
you are doing a modular operation then
it is better to reduce each of the
individual numbers and perform the
operations okay so that will make your
computations easier
so now we actually I mean so this is we
actually shift our focus and go into a
little bit of field theory okay we are
now fields are actually very central to
the understanding of crypto okay that is
for example the common the that is the
recent standard which is known as the
Advanced Encryption standard relies
heavily on finite fields okay so
therefore we will try to understand some
of the basics of fields okay that is
what are what are fields and what are
the properties of a mathematical field
okay so let us start with something
which is called semigroups
okay so first of all let us define
something which is called a
transformation or an operation so here
is an X is a set and let us define a map
which is defined by the circle as
nothing but our transformation which
takes two numbers from this set X let it
be x1 and the other one is x2 and
perform an operation
so therefore this an example of this
could be an addition okay that is just a
simple plus in the interior domain or a
multiplication so so the so if I
generalize it means that I just I just
take two numbers from the set X and I
perform these computations okay
and therefore this element so therefore
this transforms an element X 1 comma X 2
to the element X 1 operation X 2 and
this is so therefore this just simple
transformation okay so now the some of
the 3d view classes okay that is so here
is an example like examples of this
transformation as I told you that
integer is one example similarly you can
also define in the residue classes like
the if you just take two residue classes
a plus MZ + v plus MZ so this was just
so you know what is n plus MZ + v plus
MZ and if I just would consider I need
to find out the sum of these residue
classes then this is nothing but a plus
B plus MZ okay similarly the product of
the residue classes a plus MZ + v plus
MZ is equal to a multiplied by B plus MZ
ok so this is the same thing which I
just told you before this that is if I
need to kind of multiply or add to large
numbers in a modulo M domain then I just
find the remainders right and just add
the remainders or multiply the
remainders this this is perfectly fine
okay so now an operation this circle on
X is associative so we know we would
like to define as utility of this it
means that if a operation B operation C
and if I do this it can also be
associated as this operation can be also
performed as this that is a operation B
operation C being given a priority and
this holds for all ABC at in X okay so
this is how as TD with is defined and we
know what is community VD tivity which
means that if a operation B is same as V
operation a for all a and B in X then it
is said to be commutative through so
examples we know that integer addition
is an associative operation right and it
is it commutative also it's also
commutative okay but what about an
example which is not commutative
for example matrix multiplication is not
commutative we know that if I take two
matrix a and matrix an electricals B and
if I multiply a and B then it may not be
the same as that of B and a okay so now
we define what is meant by a semigroup
so it says that there is a pair H so H
is a set and we define a transformation
as just as we told right now so it
consists of a set H and anesthetic
operation so that means if the operation
is also associative on H and then it is
called a single okay so semigroup means
simply that there is a set H with an
operation circle and this operation is
also associative so if the operation is
also associative then if the operation
is associative then we say it to be a
semi-coma now the semigroup is also
called abelian or commutative if the
operation is also commutative okay an
examples of this would be like the
integer set the addition defined over it
integer set multiplication defined over
it the residue class set and the
addition defined over J's and the
residue class set and multiplication
defined over this okay so we know that
these are examples of abelian or
commutative semi groups because this is
also associative because it is semi
group and also further its abelian or
commutative so which means you can do it
either as a operation B or as B
operation a for all a and B which
belongs in the set so so the
implications are as follows so there are
some interesting
patience so let H and this operation be
is defined a semigroup and let us define
like a let us define some powers of a
okay as follows so a power 1 is nothing
but a and a power n plus 1 is defined as
a operated with a power n so this is a
recursive definition of a power n plus 1
for all for a which is in H and natural
value of n ok so the natural number n so
now if I need to compute a power in and
operate it with a power M then the same
as doing as a power n plus M ok or if I
do as a power in and take a whole power
n then which is same as doing a power in
M ok where a is in H and n and M are
nothing but natural values or natural
numbers now you see that it is a further
interesting result which says that if a
and B are in H and we perform the ambhi
and if a and if the operation is
commutative that is if a operation B is
same as B operation a then a power then
a operation B and if I raise it to power
of n is same as a raised to power of n
operated with B raised to power of n so
we can actually reflect upon this I mean
these are kind of definitions ok and we
can actually I mean we can actually
reflect upon this definition bye-bye for
example choosing the value of n to be 2
okay so let us take n is equal to 2 and
consider the operation as a
transformation B raised to the power of
2 so we know that we can actually write
this as a power B by our recursive
definition as a power B okay so now we
apply we know that this is this this
operation is so the first thing that we
start with is this so that is the first
definition but since this is a semigroup
so we know that is associative so we can
actually do like a B operation a
operated with B and we know that because
if I apply commutativity then we can
actually write this as a with B and we
know that again we can actually do this
that is a apply associativity and
perform this operation like this and
this is nothing but a square operated
with B square okay
so therefore this you can actually
inductively apply and obtain the result
that is a operated operation B if I
raise it to the power of n is same as a
raise to the power of n operation
operated with B power n so now we let us
define some something which is called
monoids okay so first of all one of the
definitions of central definitions of
monoids
is something is called a neutral element
okay a neutral element of the semi group
H operation is an element e in H which
satisfies e operation a as same as a
operation E and that that means that is
equal to ei okay for all a in H okay so
therefore the you see that an easy way
of understanding the neutral element
would be to consider an example okay so
let us consider the example of let us
consider the example of for example a
field of Z and a simple mean so the in
de are set then in de are set and there
is a plus operation define okay so we
have just defined that this is a is an
example of so this was an example of the
semi group okay so we have defined what
is meant by a semi group and let us
consider this particular example and see
that how or rather what is the neutral
element in this set so I think we all of
us know what is the neutral element in
this set so if I so that by the
definition it means that if I take a and
if I apply the operates operation class
okay and there should be a neutral
element a so that I get back a okay or
so this is called the right neutral
element okay and similarly there is
something is called a left neutral
element which says that if I add II with
a and if I obtain a so this is the left
neutral element okay so is that I write
neutral element and this is the left
neutral element then I get back a okay
so now you see that this defines that so
this actually gives us an idea that this
e is nothing but zero alright so for
example if I add a with zero then I get
back a and if I add 0 with a I also get
back in so zero is the neutral element
in the semi group Z plus similarly all
so therefore
semigroup contains a neutral element
like this then it is actually defined to
be something which is called a monoid so
so a semigroup has there is a result we
say that a semigroup has at most one
neutral element and this is actually not
very difficult to prove okay so the
first result that we can actually kind
of reflect is that the left Deuter
element and the right neutral element
are the same okay so if I just consider
the left neutral element so the left
neutral element and the right neutral
element are the same why now you can
just say that okay the left the left
neutral element be e1 and let the light
neutral element be e2 okay so what about
II one operation with E 2 now you see
that if I just think that this is the
left neutral element then by the
definition I know that e 1 operation
with e 2 should be e 2 ok because this
is the left neutral element
now what if I think this to be the right
interval like if I just think that e 2
if I think that e 2 is the right neutral
element then I know that II 1 operation
with e 2 will be e 1 so therefore from
here I understand that u 1 and E 2 are
the same right so therefore the left
neutral element and the right neutral
element are the same now the other thing
that holds is that if there is one
neutral element then there can be at
most 1 right into the image ok so this
proof I can I mean it is quite easy
actually you can follow the similar
principle but I lift these are an
exercise that is if there is a left
neutral element okay that is for a left
left neutral element there can be at
most one right neutral element
okay so so therefore so from here we
know that if there can be at most one
right neutral element that this right
neutral element is again the same as the
left neutral element by this definition
so there can be at most
so from these two results we can
conclude that there can be at most one
neutral element okay so therefore is the
semigroup which essentially has a
neutral element which is called a monoid
okay can have at most one neutral
element okay
so therefore this result holds two that
is a semigroup has got at most one
neutral element now if e which belongs
to H is a neutral element of the semi
group okay am and of the semi group and
then B also belongs to H then there is a
definition of inverse is like this that
is if I take a and if I operate it with
B then this is same as and it is same as
B being operated on a and I obtain back
II okay so for example when I am doing
when I consider the semi group Z comma
plus then what will be the inverse of a
it will be minus a so because if I know
that if I add a with minus a then I
obtain back the neutral element which is
so if a has an inverse then a is called
invertible in the semi group H and in a
monoid each element has at most one
inverse okay so this also result can be
proved that is if there is a monoid so
the monoid then each element has at most
one inverse so examples are like this
that is if I consider Z comma plus the
neutral element is 0 and the inverse is
minus a if you consider zit and
multiplication the neutral element is 1
and the only invertible elements are
plus 1 and minus 1 because if I just
consider any other integer like say 5
then there is no integer say into your
number with if you multiply with which
you will obtain that the neutral element
except so therefore the neutral element
exists only 4 plus 1 and minus 1
whatever the residue class dead /mz
plus and the operation is plus then
neutral element is MZ itself okay and
the inverse is minus a so this should be
actually minus a plus MZ ok so it means
that if I take if I just consider this
particular set that is
z MZ which is a semigroup and then the
operation is defined as plus then a
neutral element is MZ that is the
neutral element and the universe is so
this is a neutral element and the
inverse is minus a plus MZ okay so that
is the inverse okay and you can verify
this it's quite simple so so what about
z MZ and one product z MZ comma product
in this case the neutral event is one
plus MZ and the inverse and this result
we will see actually is are those
elements T which have actually which are
actually co-prime to em okay that is
every element does not have an inverse
but only those elements for only those
elements inverse exist which are
actually co-prime to em so which means
that the GCD or the greatest common
divisor of that number and M is actually
equal to one okay so we will see this as
we go ahead so then we define what is
called a group a group is a monoid in
which every element is invertible okay
so a group is a monoid in which every
element is invertible and the group is
commutative or a million if the monoid
is also commutative so examples of this
will be like Z comma Plus which is an
abelian group and Z product which is not
a group okay so so this is actually not
an example of fair group and then we
have got Z comma M s MZ m plus z slash
MZ and Plus which is an abelian group
okay so why is this not a group this is
not a group because from the definition
of a group a group is a monoid in which
every element is invertible okay and we
have just defined just discussed in the
previous slide that is in this
particular set only invertible elements
are plus 1 and minus 1 so every element
does not I mean rather every element
does not have does not have an inverse
therefore Z comma multiplication is
actually not a group because every
element is not invertible in this is not
invertible in the semi group okay so
therefore that is the that is the
definition of a group and there is a
higher concept to this which is called
the ring and ring is nothing but R and
there actually is a triplet so there is
not only one
operation as plus and there is another
operation also along with it such that R
comma plus is an abelian group the way
we have defined an R comma product is or
R comma the second operation is actually
a Monon okay in addition it satisfies
the property of distributivity which
says that X if you want I mean if we
product take product with y plus said
then it is same as X dot y plus X dot
set for XYZ which belongs to this ring
the ring is also called commutative if
the semi group R comma dot that is this
one is also commutative okay and a unit
element of the ring is a neutral element
of the semi group R comma dot so the
unit element of the ring is a neutral
element of the semi group R comma dot so
therefore the neutral a unit element of
this ring we defined as the neutral
element of this of the monoid r comma
dot so then we define what is called a
unit group which means that let R be a
ring with unit element and element a of
R is called Emotiv L or a unit if it is
invertible in the multiplicative
semi-group of R so an element a I repeat
this definition a element a of R is
called invertible or unit if it is
invertible in the multiplicative
semi-group of our okay that means
multiplicative semi-group of r will be
this okay so if it is invertible in this
particular semi group then it is said to
be invertible okay and the element a is
called a zero divisor if it is non zero
and that is if the element itself is non
zero and there is a non zero B in R such
that if I take the product of a and V or
the product of B na then we get back
zero okay now units of a commutative
ring actually form a group and this is
called the unit group of the ring and it
is often denoted by art star okay so
that is the definition of a unit group
and you can actually have one very I
mean some example because I think this
is little abstract so in order to
understand this let us take some
examples okay so let us consider the set
or let us consider the ring z MZ and
let us define let us define now rather
let us take the value of M to be
something like 10 okay so we know that
the elements here will be like 0 1 2 and
so on till 9 okay so now you consider
like whether all the elements so let us
consider like some less consider some
interesting facts okay let us consider
the numbers for example 2 and let us
consider like let us multiply 2 with all
possible elements which are there we all
possible nonzero elements which are
there in this same so let us consider 2
into 1 2 into 2 2 into 3 2 into 4 2 into
5 and so on okay so if you consider
these multi this product and if you take
the modular 10 operation that is if you
take mod 10 for all of them then you
will find that this is actually equal to
2 this is actually equal to 4 this is 6
this is 8 but this one is 0 so this
shows us an example where there are two
elements which are nonzero like two is
also non zero and five is also non zero
but if I multiply this and if I take I
mean in this part if I take a modulo 10
then what I obtain back is 0 so
therefore from this definition we say
that 2 is actually a zero divisor ok the
element 2 is actually a zero divisor so
therefore this particular thing I mean
therefore in this this is an example
which shows that zero divisors exist
ok so therefore let us come back to this
and see that the element a is called a
zero divisor if it is a non zero and
there is a non zero being are such that
a multiplied with B or B multiplied with
a zero okay so this is an example to
understand this particular aspect now
what about this an element a of R is
called invertible or unit if it is
invertible in the multiplicative
semi-group of our okay so let us see
that among these particular I mean
numbers like 0 1 2 9 what are the
elements which are invertible okay so
let us leave out because 0 is obviously
not invertible let us consider one so we
know that if i take 1 and multiply it
with one I get back
one itself what about two so if I take
two and if I multiply with any of the
numbers will I get back one so actually
we will see that no you will not get
back to is not invertible okay so the
numbers which are invertible in this
particular set from zero to nine can
actually be found out like this okay so
there is it will be 1 similarly 3 will
be invertible 4 will not be invertible 5
will not be invertible 6 will not be
invertible 7 will be invertible 9 will
be invertible 8 will also be invertible
sorry 8 not will not be invertible 9
will be invertible and the reason rather
the one easy way of checking is that if
I take the GCD of any of these numbers a
and with in okay if a is invertible then
this GCD of a and 10 should be equal to
1 okay so if the GCD of a comma 10 is
equal to 1 then we will say that a is
invertible so a is invertible if and
only if the GCD of a comma 10 will be
equal to 1 so that means we will find
that this particular set that is 1 3 7
and 9 will actually form something which
is called a unit group okay so therefore
if we form a unit group I mean this open
defined as R star in this ring okay so
we will see more examples of this but we
will as we proceed we will see more
examples of this so let us consider the
zero divisors okay so therefore the zero
divisors of the residue class z slash MZ
he is actually a plus MZ and this is a
generalization of what we said there are
zero divisors of the residue class z
slash MZ is actually a plus MZ such that
that will take the GCD of a and with M
then it is neither 1 not M but it is
somewhere in between so there is a
non-trivial GCD of a and M okay and the
proof is very simple it says that if a
plus MZ is a zero divisor of z slash MZ
then there is an integer B this follows
strict on the definition such that a B
is congruent to 0 modulo M but neither a
nor B is 0 modulo M so which means that
M divides a B so a B is congruent to 0
means M divides a B but neither a not B
is actually divisible by M so this
automatically implies that if I take the
GCD of a and M then this should be some
significant value okay that is it means
that if you take M so so there it says
that a B is congruent to 0 modulo M
right so that means that a B will be
equal to I mean another M divides a B
right so if a M dy it's a B so which
means that AV divided by rather AV
divided by M this should be a number
right this should be an integer number
this is an integer value but we know
that neither a nor B are actually
divisible by M okay so therefore a by M
is not an integer B by M is not an India
okay
so that means that a and B definitely I
mean I mean there should be a
cancellation between a and M okay and
that means that the GCD of a and M
should be actually something which is
between one at M so it is neither one
nor M see for example if you just
consider the example just touch now
where what we consider with M is equal
to 10 and a being equal to 2 and B being
equal to 5 okay so now let us consider 2
into 5 divided by 10 this ratio okay so
you will see that 2 into 5 by 10
therefore it means that the GCD of this
particular thing is actually not equal
to it is not is neither 1 not 10 but it
is in between okay so therefore this
shows that there should be a I mean
there should be a number D which divides
both a and D also divides M okay so
there should be a number D and that
number is neither D is not neither equal
to 1
Noorie 9 is equal to M ok so this proves
that this shows that M divides a B but
neither a naught naught naught B and
therefore this implies that the GCD of a
and M lie
is between 1 and M now conversely if one
this lesser than equal to GCD is less
the GCD is a comma M less than M then
define then if I define a number B as M
divided by GCD a comma M okay then both
a and B are non zero modular M so then
both a and B are non zero modular m that
is true from the definition itself right
but if what if what if I multiply a and
B so if I multiply a and B then what I
obtain is a so if I if I take this
definition of M divided by GCD of a
comma M and if I multiply this with a
then I obtain 0 modulo M the reason is
if I if I multiply this with a and there
is a GCD of a comma M then this divides
a and therefore what I obtain is an
integer multiple of M and therefore if I
take a congruence of another if I divide
it by M and take the remainder then the
remainder is 0 so this proves that a B
is congruent to 0 modulo M thus a plus
MZ is a zero divisor of z slash MZ so
therefore we will see that I mean 0
devices I mean it is very easy to detect
the zero devices how I mean because we
just this simple test reveals the zero
devices so if I take G CD of a number a
and along with a with M and if the GCD
lies between 1 and M then actually it
forms the zero devices so there is a
natural corollary to this that if P is a
prime then state that plus red slash PZ
will have no zero divisors because
because if I take the GCD of a number
with P then it is always equal to 1
because that is the definition of
primary T right so that means that it
automatically implies that there are no
zero devices if P is a prime number in
this particular set /pz so then we come
to the definition of field which says
that field is a commutative ring Arts
Plus multiplication in which every
element in the semi group our
multiplication is invertible so
therefore if every element is invertible
then it is a field so examples of this
will be like the set of integers is not
a field because you know why I mean the
set of integers cannot form a field
because every number is not invertible
the set of real and complex numbers for
Mayfield and the residue class modular
prime number except zero is a field why
because if we are seeing that because of
this particular result if P is a prime
then Z / TZ will have no zero devices
okay so that automatically implies that
this is not a field so then we come to
the concept of euler totient function
which says that if a is greater than
equal to 1 and m is greater than equal
to 2 or integers and if GCD a comma m is
equal to 1 then we say that a and M are
relatively prime okay now the number of
integers in Z M where m is greater than
1 that are relatively prime to m and
does not exceed m is denoted by Phi m or
which is also call as the euler's
totient function or phi function so
therefore we we start with this define
it is a recursive fashion and it says
that Phi of 1 is equal to 1 ok now what
about let us consider Phi of 26:26 is
the number of English letters which are
there and let us consider the value of
Phi of 26 we can see that Phi of 26 will
be equal to 13 okay if P is a prime then
Phi of P is P minus 1 and if n is equal
to 1 to 24 then the values of Phi n are
as follows ok so this is just an
enumeration so so you will see that you
can verify these results but the fact is
that this function is very irregular
that is you will not find any distinct
even modernist entities like it is not
like as n increases Phi n always
increases okay you can see that there is
a deeper times also ok so now let us see
the properties of Phi n so there is a
very interesting result which says that
if MN NF relatively prime numbers then
Phi of MN is nothing but the product of
Phi M and Phi n now this result is very
interesting and helpful to compute the
Phi of the higher numbers or larger
numbers for example Phi of 77 is same as
Phi of 7 multiplied by 11 which is same
as Phi of 7 multiplied by Phi of 11 and
we know that if 7 is a prime number then
Phi of 7 is nothing but 6 and Phi of 11
is nothing but 10 so the product is 60
similarly Phi of 1 8 9 6 divided that
mean if I obtain the prime factorization
so I can obtain the result of 6 24 so
this result can be extended to more than
two arguments comprising of pair
wise co-prime integers so let us see
some interesting results okay there is
he says that if the first result says
that if there are M terms of an
arithmetic progression a P and has got
common differences which are prime to m
then the remainders form Z M okay so if
there are M terms of an arithmetic
progression and has got common
difference that is if the common
difference is prime to n then the
remainders form Zn so this is a quite
simple result which you can check the
other one says that in an integer a is
relatively prime to M if and only if its
remainder is relatively prime to m so if
an integer a is relatively prime to m
then it automatically it's an
bi-directional implication is that the
same as saying is that its remainder is
also relatively prime to m and the other
interesting result is that if there are
m terms of an AP and has got a common
difference prime to m okay then it is
actually a the combination of these two
results which says that then there are
Phi M elements in arithmetic progression
which are relatively prime to M because
so you can follow like because it says
that the remainders form ZM and you know
that if the remainders form Z m and and
because I mean an integer is relatively
prime to n only when the remainder is
relatively prime to m so we actually
need to find out the number of
remainders which are relatively prime to
m and that follows from the definition
as Phi M right so therefore if there are
M terms of an arithmetic progression and
the common difference is also prime to m
then there are actually five m elements
in the arithmetic progression which are
relatively prime to m so we will apply
this result to obtain this nice reserved
midnight or nice observation so let us
consider Phi of a men so we know from
the definition Phi of MN means those
numbers or other means the number of
values inside from 1 to M n minus 1
which are actually co-prime to m n okay
so let us now arrange these numbers from
1 to M L minus so this is nothing but m
minus 1 n m sir is MN minus n plus n so
this is MN so therefore from 1 to M n
all these numbers are we have arranged
them in this fashion okay so it is like
1 2 and so on till N and
so you arrange them in this fashion so
now you consider that among these
numbers if you need to find out
so if since M and n are relatively prime
if a number is relatively prime to MN
then it has to be relatively prime to
both m and both M okay so now you see
that there are I mean among these
numbers if you consider like this number
like for example is so so you will find
that there are Phi n columns okay that
is there are Phi n columns in which all
the elements are co-prime to n so if you
see that for example this particular
column there is a last column that is NN
plus 1 this this column all the elements
are not co-prime to n okay because this
is actually you will find that n
multiply this n plus a and this M minus
1 into n plus n and so on okay so that
means that we need to find out the
number of columns okay in which all the
elements are co-prime to n and we know
that the there are actually five n
columns in which all the elements are
co-prime to n now among these columns
which are actually co-prime to n we
would like to find out what are the
numbers which are actually co-prime to M
so we see that we apply the previous
result and see that for example let us
consider this okay so in this particular
column so assume that K is actually
co-prime to n and consider this column
and the result says the previous result
says that if so what is that what is the
what is the difference here what is the
common difference the common difference
is K okay so now if this K is actually
therefore co-prime to n okay then the
previous result says that if there are M
terms of an arithmetic progression and
as a common difference which is prime to
m then there are five Phi M elements in
arithmetic progression which are
relatively prime to m so that means that
these are I mean there are Phi M
elements which are actually co-prime to
M so if there are five elements here
which are co-prime to n and there are
Phi n elements which are actually M in
which all the elements are co-prime to n
then combining this we obtain that the
Phi M into Phi n where numbers which are
actually co-prime to both m and both N
and that actually comes us Phi gives us
the number of Phi MN so the so therefore
we come
like thus there are Phi n columns with
Phi M elements in each which are
co-prime to both m and n and thus there
are Phi M into Phi n elements which are
co-prime to mm this proves the result so
we can actually apply this result and we
can obtain some interesting observations
like Phi P to the power of a will be
equal to P to the power of a minus P to
the power of a minus 1 and it is quite
evident for a equal to 1 but for a
greater than one of the elements 1 to P
P to the power of a the elements P P
squared P to the power of a minus 1
multiplied with PR not coca into P to
the power of a the rest will be co-prime
so therefore we can obtain like Phi P to
the power of a will be P to the power of
a minus P to the power of a minus 1 and
that is actually equal to P power of a
into 1 minus 1 by P we can actually
extend this result and apply this like
follows and compute the Phi of any value
in this paper you know from the
fundamental theory of arithmetic that we
can actually take in and obtain Phi P
and we can obtain its prime
factorizations then it will be easy to
compute the value of Phi n ok so that
means that the factorization of n is
available then computation of Phi n can
be obtained using this companies this
formula so for example if I need to
compute Phi of 60 then we can obviou and
we know the prime factorization of 60 as
4 multiplied by 3 multiplied by 5 then
Phi of 60 is 60 into 1 minus 1 by 2 into
1 minus 1 by 3 into 1 minus 1 by 5 okay
so we that is this is equal to 2 square
okay so therefore this is just straight
away application of this result so then
we see that just let us conclude our
today's talk with a theorem of format
which say that it is called formats we
do theorem and it is very useful okay so
it's so you see that if GCD of a comma M
is equal to 1 then a power Phi M is
actually congruent to 1 modulo M
actually this result this Euler Fermat's
theorem and a variation of this is
saying as far as theorem it says that if
Informers to do theorem is this M is
actually prior prime number lemmie and
we know that if Phi M ap is prime then
Phi of P will be equal to P minus 1 and
therefore a to the power of P minus 1
will be congruent to 1 modulo P that is
farmers to the theorem but let us
consider
the generalized theorem and let us
consider a set R which is formed of R 1
to R Phi M we know that there are Phi M
elements which it forms a reduced set
modular M now if GCD of a comma M is
equal equal to 1 you see that a
multiplied with R 1 so you just take
these numbers and you multiply each of
them with a ok now this if GCD of a
comma M is 1 then this is also a reduced
system modulo M ok now this will just be
a permutation of the set R so VG's we
have considered now we have considered
one example previously where we have
seen that if you are taken some numbers
and those numbers essentially we are
nothing but a rearrangement right like
if you see that the previous example of
this this this particular set so this
particular set was just a rearrangement
of the original of the original
remainders ok so therefore similarly I
mean by applying this if you just take
these set of remainders and if you
multiply them with a number a which is
cosine to M then you obtain another
order of the of the remainders ok so now
if we just take therefore therefore it
is basically the same set of remainders
but in some other order
so therefore the product of these
particular elements will of these
elements will also be the same so if I
just take these numbers and I multiply
them this should be the same as the
product of these numbers so that means
writing them I mean one for me this will
work out to be a to the power of Phi M
because there are Phi M numbers and on
the left hand side you will have R 1 to
R Phi M multiplied on the right hand
side you will also have R 1 to R Phi M
multiplied now note that since these
numbers are actually co-prime with M
therefore there can be cancelled out and
therefore what remains is a power Phi M
is congruent to 1 modulo M ok and that
is the euler formats formula so example
of this can be applied to find out very
interesting results like suppose 72 ^
1001 is divided by 31 and we need to go
argue that so we know that 72 is nothing
but equal to 10 modular 31 hence 72 ^
1001 will be equal to 10 to the power of
thousand 1 modulo 31 now if I apply
farmer's theorem then since P is a prime
number then 10 to the power of 30 should
be equal to ax comma going to 1 modulo
31
note that 31 is prime
for raising both sides to the power 33
will be 10 to the power of vinyl Dan 90
is congruent to 1 modulo 31 and
therefore we find that this can be
worked out like this 10 to the power of
thousand 1 will be 10 to the power of
990 which is the nearest number and
these are the subsequent remaining
numbers so similar numbers the small
numbers you can reduce quite easily and
apply the previous results to do these
computations then you can see that this
will work out to 19 modulo 31 similarly
you can work out this example take this
as an example exercise that is fine the
least residue of 7 to the power of 973
modulo 72 note 72 is not a prime number
so I conclude here and we have followed
these texts from talung and from bushmen
for the for this power part and next
day's topic would be probability and
information theory
you