Understanding Reduced Residue Systems Mod 7: Can You Help?

[1+1=1]

i need help understanding modulos. i have no grasp on the information and i am wondering if you people can help me. i need to show that the number 3, 3^2, 3^3, up to 3^6 form a reduced residue system mod 7.

also, i need help with this... if p and q are distinct prime,s, prove p^q + p^p is congruent to p+q (mod pq).

i will post my ideas in a little bit my computer is acting weird!

any assistance will be appreciated!

 

[matt grime]

What is the definition of a reduced residue system? What do you need to show those powers of three satisfy? Do they? If you can't show that, why not? You are posting a lot of questions on this subject, which is a good thing, but you'renot showing that you've thought about any of the questions you ask before posting. As I find myself saying a lot these days maths is just about following sets of rules. Always write out the definition of what you're asked to show if you can't show it straight away, how do the definitions relate to what you're asked to prove? From the level you're at now, the results you are asked to prove are not magically true for some amazing reason, they will almost all follow from the definitions directly and quite possibly will be almost identical to an example in your notes. Your lecturers will not be trying to catch you out, and also will not be trying to make you show you're the next Erdos (we can tell without having to try to hard if you're a Field's Medal potential), you won't have to think to far out the box.

 

[1+1=1]

Matt- sorry again, as i said i am new to this and i am just assuming that everybody knows what everyone else is talking about. honestly, didn't mean to tick anyone off. also, i know I'm not the smartest person in math, i just want to understand this stuff just long enough to pass a class, and then i'll probably forget it forever... you won't use what you don't understand. sorry for not definining everything and i DO know mathematics is a formula, i just need to know how this stuff fits in there.

ok, the definition of a reduced residue system is any set of phi(m) integers that are relatively prime to m and that are mutually incongruent modulo m. an example of this is phi(8)=4, and the numbers are {1,3,5,7}. another example is {9,-5,21,7}. also, it basically means that take the integers up to m. i .e. 8 = 1,2,3,4,5,6,7,8. cross off the m, which would be 8. then cross off the multiples of 8, which are 2,4,6. you are left with the reduced residue system, =>{1.3.5.7}. is that any better ? please feel free to critique me any time because it is by this that i can relate these definitions to other items in class, in the book, and on the exam. thanks matt.

 

[Gokul43201]

You are taking a number theory course...and want to learn the stuff to just pass an exam ? I find that most surprising. Surely, this is not a required course unless you are a math major ! And if you are, you'd better want to remember what you are learning.

Find the residues of the powers of 3 (mod 7), and see what you get.

 

[robert Ihnot]

Matt: It is not true that p^q + p^p == p+q Mod pq, try p=2, q=3. You might consider p^q + q^p ==p+q Mod pq.

 

[matt grime]

So, take the advice in my post. You know what a reduced residue system is, now, do all those powers of three satisfy the requirements? What must you show? If you can't show it why not? There are six powers of three and there need to be six elements in a set of reduced residues mod 7, so that only leaves one thing to show, which is...? I know what the definition of reduced residue is, however the idea you should write down all the information you know and all the things you need to know was to help you solve the problem, not to help me solve the problem. That's how you start doing the questions.

 

[Gokul43201]

Matt: It is not true that p^q + p^p == p+q Mod pq, try p=2, q=3. You might consider p^q + q^p ==p+q Mod pq.

I'm sure you're right. The latter follows easily from the Little Theorem.

We know from the LT that a^p==a(mod p). So, in particular, q^p==q(mod p).
Also, obviously q^p==q (mod q). Thus, q^p==q(mod pq).

The other half follows in the same manner. Add the two expressions to get the desired result.

 

[1+1=1]

Find the residues of the powers of 3 (mod 7), and see what you get.

i did and i got 3=3, 3^2=2, 3^3=6,3^4=4,3^5=5, and 3^6=1, all mod 7. thanks guys for helping me.

would this go the same way? find a reduced residue system mod 7 composed completely of multiples of 3?

 

[Gokul43201]

Yes, except you have to work backwards. Of course, the previous question itself provides one such solution.

 

[1+1=1]

amazing! this stuff is making more and more sense to me, i just hope it isn't too late to be learning it. LOL btw, does anyone know or link me to a good proof of why .999=1? my girlfriend and i were almost fist to cuffs over this, she saying "that's impossible", while i countered saying "anything is possible"

 

[Gokul43201]

I believe there have been several discussions of this right here. There was a recent one in the Logic subforum, I think. Try Googling ".999... = 1" with "physics forums" .

 

[matt grime]

Well, what else does it equal. Here are three proofs in increasing order of correctness.

1: 1/3= 0.3... we all agree, hence multiply both sides by three, and get 1=.99999...

2: 0.99... means the infinite geometric series 9/10+9/100+9/1000+... that sum is easily calculated by any high school student to be 1 using the formula

3: 0.99... means the limit as n tends to infinity of the cauchy sequence of its partial sums, (like 2), since difference of this cauchy sequence and the constant sequence 1,1,1... is a cauchy sequence that tends to 0, these two elements are by definition of the real numbers equal. This is two but more formally. Do either you or your girlfriend know any definitions of the real numbers? They are, most usefully, the completion of the rationals in the oridnary norm (using cauchy sequences) or the unique ordered complete field, from these definitions the result follows simply. The reals are NOT synonymous with decimal expansions though lots of people seem to think they are.

 

[kuenmao]

Let x=0.999...
Then 10x=9.999...

10x-x=(9.999...)-(0.999...)
9x=9
x=1

How does that work?

 

[matt grime]

These kinds proofs are not very, erm, can't think of the right word, but compelling, I suppose, as counter arguments to the cranks, since they require you to define how to do arithmetic operations on infinite strings, and don't make explicit use of the definition of what the real numbers are. I only say this because the standard crank view is to refuse ot believe that you can do arithmetic with infinitely long strings of decimals, and they always go on about the 'last' place in the expansion and so on. So, whilst they are perfectly good for me, they leave too much room for the 'disbelievers' to rebut them. However, some would view the hiding of the definition of the real numbers as a good thing as it may cause too many questions that are difficult to answer. You pays your money and takes your chance...

 

[1+1=1]

would anyone object if i put more ?'s on here for assistance, provided i tell everyone what i think about them so far? i know i just can't GIVE a problem and expect to get answers w/o my own thinking of it too. can anyone agree with me on this? i simply will not just put up the ? and expect to get an answer, i will post a ? and tell what i have so far on the problem, and then have assistance? anyone please let me know... i have some good ?'s

 

[Gokul43201]

Yes, ask questions.

Remember, '?' is a 'question mark.' It is a form of punctuation used to terminate an interrogative statement. It is misleading to use it as an abbreviation for the word 'question'...especially for people wo are not aware of your style.

Try and post new questions on new threads with helpful subject names. This makes it easier for searching and referencing.

 

[1+1=1]

thank you thank you all.