Understanding Congruences: Residues & Euler's Totient Function

[AlbertEinstein]

I am finding it very difficult in understanding congruences.i have understood what congruences are and their basic properties .But i am stuck at the next junction about residues.After that i understood euler's totient function.

Well can anyone describe in detail about residues with sufficient examples as the book has none?
thanks

 

[AlbertEinstein]

What happened? No one gave any answer to my question.Hey guys, please help.Please explain about residues.

thanks

 

[matt grime]

Explain what?

 

[shmoe]

It's hard to know where to start (and stop) with a question like this. You'll get a much better response if you can narrow it down more.

If you are finding your book is lacking, get more from the library. Look for "Elementary Number theory" books.

Also, there have been plenty of congruence questions asked on this forum, so your can search around for some examples here.

 

[AlbertEinstein]

Well the author writes:

Def~ If x \equiv y (mod m) then y is called a residue of x modulo m. A set x_{1},x_{2},x_{3},...,x_{m} is called a complete system modulo m if for every integer y there is one and only one x_{j} such that y \equiv x_{j} (mod m).

What I do not understand is the concept of "complete system modulo m".Also the author then introduces "residue class" which also troubles me.
I think that lack of examples in the book may be the reason.Please explain the above two concepts with few examples.

 

[HallsofIvy]

If, for example, m= 5, then x \equiv y (mod 5) if and only if x- y is a multiple of 5: y= x+ 5n for some integer n. In particular, 0, 5, 10, 15, 20,... all multiples of 5 are congruent. 1, 6, 11, 16, 21, ... are congruent, 2, 7, 12, 17, 22, ..., are congruent, 3, 8, 13, 18, 23, ... are congruent, and 4, 9, 14, 19, 24, ... are congruent. There are 5 conguence classes which can be represented by one member of each conguence class. Any member of a class is a "residue" for any other number in the class. A "complete system modulo 5" is a specific choice of exactly one member of each class to represent each. Although it is not necessary, it is often simplest to choose the smallest non-negative number in a class to represent that class. That is, one "complete system modulo 5", and probably the one most used, is {0, 1, 2, 3, 4}. That's where the name "residue" comes from: it is the remainder (what's "left over") when we divide the number by 5.

 

[AlbertEinstein]

Thanks, I understood.
Now the author writes about" reduced residue system modulo m "
Please explain.

thanks.

 

[matt grime]

This is straight forward, as long as no one tries to get you thinking about equivalence relations unnecessarily.

Fix m.

Just think of the integers R={0,1,2,..,m-1}. Now we can add and mutliply elements of R and if we take the remainder upon division by m, then + and * (for multiplication) make R behave like the full set of integers. Properly we are saying that R with + and * modulo m is a ring.

Now, we have _chosen_ to use the symobls 0,..,m-1 for this definition. But really I didn't need to, I just did it for simplicity. I can, for instance use m instead of 0, then m acts like the identity element for addition. In fact all I need to do to define a ring here is pick m integers, no two of which are equal modulo m, and I can define addition and multiplication modulo m, and since I have enough of these symbols (this is the complete part) then I will get something well behaved.

Examples, take m=3.

{0,1,2} with addition and mutliplication defined modulo 3, or {3,7,14} where I define 3*7=3 and so on.

Of course there is an obvious best choice for any such system, 0,1,2,..,m-1. This is usuall called the (complete) reduced residue system.If you need to know about a residue class, well, congruent mod m is an equivalence relation, and the equivalence classes are the residue classes.

 

[AlbertEinstein]

Can these all be explained without the help of ring? I haven't done any course on algebra.

If not please explain in brief what a ring is?

 

[matt grime]

Then forget rings, it is not necessary to know what the definition of a ring is - you don't need to know what the definition of a ring is to understand what the integers are, or integers modulo something.

 

[shmoe]

Of course there is an obvious best choice for any such system, 0,1,2,..,m-1.

This isn't what I know a reduced residue system to be, a reduced residue system is a set of representatives for the units of Z/nZ, equivalently the classes whose representatives are coprime to n, equivalently those with multiplicative inverses mod n (the 'equivalentlys' are for Albert's benefit).

For n=6, some complete residue systems:

{0,1,2,3,4,5}
{1034,1035,1036,1037,1038,1039}
{0,7,14,3,-2,5}

some reduced residue systems:

{1,5}
{1037, 1039}
{7,5}

You can get a reduced residue system from a complete one by tossing the residues that aren't relatively prime to n.

 

[AlbertEinstein]

"Z/nZ" -- what does this mean?

"You can get a reduced residue system from a complete one by tossing the residues that aren't relatively prime to n"----what is the benefit?

 

[shmoe]

"Z/nZ" -- what does this mean?

That's some ring notation, the factor ring of the integers Z by the ideal nZ. You can just think of the set {0,1,..., n-1} with + and * defined on them as usual for integers, then take the remainder upon division by n (matt has mentioned this). This set behaves in a similar way to the normal integers with + and *, adding two elements gets you an element back in the set, addition distributes of multiplication, you have a multiplicative identity, etc. In some ways it's very different though, obviously it's finite, when n is not prime you will have zero divisors, that is non-zero elements whose product is zero (like 2*3=0 mod 6).

It's not necessary to think of this in terms of rings or learn the notation, but it wouldn't hurt if you have the curiosity (pick up some intro algebra books if you're interested).

"You can get a reduced residue system from a complete one by tossing the residues that aren't relatively prime to n"----what is the benefit?

Sometimes these are the only elements you are interested in. They have nice properties like they form a group under multiplication and you can use some group theory results. Again, you don't need to know what a group is, you're probably going to end up proving some special cases of some of the group theory results in your number theory class. When it comes time for you to take an abstract algebra course lightbulbs should go off very often as you think back to these special cases. Of course you can always learn some group stuff on your own if you want to see the more general versions.

 

[matt grime]

Well, once more, we have a situation where one person's definition differs from someone else's. Obviously all that matters to the OP is what their book says.