A community for students. Sign up today

Here's the question you clicked on:

ganeshie8 one year ago Consider a group of relatively prime positive integers that are less than the integer $$n$$. The operation is multiplication mod $$n$$ Show that there exist at least two integers in the group such that $$x^2=1$$. assume that $$n\gt 2$$

• This Question is Closed
1. ganeshie8

for $$n=5$$, we get the set of relatively prime positive integers $$\{1,2,3,4\}$$ $$1^2=1$$ and $$4^2=1$$ are the two elements that satisfy the given condition

2. anonymous

Latex tip :) $x^2\stackrel{n}{\equiv} 1$

3. anonymous

In group {1,2,.......,n-1} , 1 is identity and 1^2=1 is always in the group. We know that (n-1) is relative prime with n, that is gcd (n-1,n)=1 or $$n-1\equiv 1(mod n)$$ $$(n-1)(n-1) \equiv 1*1=1(mod n)$$ we can use multiplication table of group to show that there is at least 2 elements on the table satisfy the condition. |dw:1439986568531:dw|

4. ganeshie8

Nice! so you're saying that $$1$$ and $$n-1$$ are relatively prime to $$n$$ and they have order $$2$$ no matter what $$n$$ is

5. anonymous

I think so.

6. ganeshie8

gotcha! thank you :)

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy