## finding reduced residue system

For discussing Olympiad Level Number Theory problems
Arif Ahmed
Posts: 10
Joined: Tue Mar 15, 2011 10:39 am

### finding reduced residue system

Let $a_1$,$a_2$,..........$a_r$ be a reduced residue system modulo $m$ and let $n\geq1$.Prove that $a_1^n$,$a_2^n$,......$a_r^n$ is a reduced residue system modulo $m$ if and only if $(n, \phi(m))=1$

SANZEED
Posts: 550
Joined: Wed Dec 28, 2011 6:45 pm
Location: Mymensingh, Bangladesh

### Re: finding reduced residue system

Firstly, Let $S_{0}=\left \{ a_{1},....,a_{r} \right \}$ and \.Now $S$ is a reduced system. So there are no integers in $S_{0}$ such that $(a_{i},m)> 1$.Hence $(a_{i}^{n},m)= 1$. for all $i< r$.Now we will prove a lemma .
Lemma: Let $R$ be a reduced system of residues mod $m$ and let $a$ be any given integer such that $(a,m)=1$,hen there exists a given integer in $R$ such that a unique integer,corresponding to $a$,say $b$ such that $a\equiv b(mod m)$.

Proof:Let $r$ be the least residue of $a(mod m)$ so that we have $a\equiv r(mod m), 0\leq r< m$ and $(r,m)=(a,m)=1$.But the set of least residues of of $R$ is just the set of all the integers less than $m$ and coprime to $m$.hat means that $r$ is an element of the set of the residues of the elements of$R$ mod $m$.it implies that there exist a uniqe integer $b$ in $R$ such that $a\equiv b(mod m)$.

From the lemma above we can directly say that $S$ is a reduced system.

There is surely a problem.It is true that $(n,\phi (m))=1$ is necessary, but where is the bug of my solution?will anyone debug it please?
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

shehab ahmed
Posts: 66
Joined: Tue Mar 20, 2012 12:52 am

### Re: finding reduced residue system

what is the meaning of reduced residue system?i don't know

Arif Ahmed
Posts: 10
Joined: Tue Mar 15, 2011 10:39 am

### Re: finding reduced residue system

Let $m$ be positive.A reduced residue system modulo $m$ is a set of integers such that every number relatively prime to $m$ is congruent modulo $m$ to a unique element of the set.

Phlembac Adib Hasan
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

### Re: finding reduced residue system

SANZEED wrote:Firstly, Let $S_{0}=\left \{ a_{1},....,a_{r} \right \}$ and $S=\left \{ a_{1}^{n},....,a_{r}^{n} \right \}$.Now $S$ is a reduced system. So there are no integers in $S_{0}$ such that $(a_{i},m)> 1$.Hence $(a_{i}^{n},m)= 1$. for all $i< r$.Now we will prove a lemma .
Lemma: Let $R$ be a reduced system of residues mod $m$ and let $a$ be any given integer such that $(a,m)=1$,hen there exists a given integer in $R$ such that a unique integer,corresponding to $a$,say $b$ such that $a\equiv b(mod m)$.

Proof:Let $r$ be the least residue of $a(mod m)$ so that we have $a\equiv r(mod m), 0\leq r< m$ and $(r,m)=(a,m)=1$.But the set of least residues of of $R$ is just the set of all the integers less than $m$ and coprime to $m$.hat means that $r$ is an element of the set of the residues of the elements of$R$ mod $m$.it implies that there exist a uniqe integer $b$ in $R$ such that $a\equiv b(mod m)$.

From the lemma above we can directly say that $S$ is a reduced system.

There is surely a problem.It is true that $(n,\phi (m))=1$ is necessary, but where is the bug of my solution?will anyone debug it please?
What have you proved?
BTW, there is no need to state or prove this lemma in such a way.(Actually it's not a lemma,direct definition of reduced residue system)
And my question, how are you using this 'lemma'?If I assume the first one is a typo,(if I assume it is $S_0$)there is still problem.Your 'lemma' has no validity then.
Just see, what you have to prove
$S\; \; \text {is a reduced residue system}\; \; \Leftrightarrow \; \; (n,\phi(m))=1$(My debugging is not so cool )
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

SANZEED
Posts: 550
Joined: Wed Dec 28, 2011 6:45 pm
Location: Mymensingh, Bangladesh

### Re: finding reduced residue system

Sorry, but actually I wanted to show that $S_{0}$ is a reduced system,not $S$. Now what will you say?
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

### Re: finding reduced residue system

SANZEED wrote:Sorry, but actually I wanted to show that $S_{0}$ is a reduced system,not $S$. Now what will you say?
That is already given.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

Phlembac Adib Hasan
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

### Re: finding reduced residue system

SANZEED wrote:Sorry, but actually I wanted to show that $S_{0}$ is a reduced system,not $S$. Now what will you say?
Same question as Mahi vaia.Please read what I wrote before:
If I assume the first one is a typo,(if I assume it is $S_0$)there is still problem.Your 'lemma' has no validity then.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

shehab ahmed
Posts: 66
Joined: Tue Mar 20, 2012 12:52 am

### Re: finding reduced residue system

আমার সলিউশনটা কেউ দেখ।আমি শিওর এখানে কোথাও না কোথাও ভুল আছে
Last edited by Masum on Tue May 29, 2012 12:19 pm, edited 1 time in total.
Reason: LaTeXed

Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
Location: Dhaka,Bangladesh

### Re: finding reduced residue system

There are nice tutorials about using LaTeX. You should read them, it is not hard at all. Just using two dollars efficiently. You certainly don't want that only you in the world would understand your post.
One one thing is neutral in the universe, that is $0$.