## 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

### 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.

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

### 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? Use $L^AT_EX$, It makes our work a lot easier!

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? 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
One one thing is neutral in the universe, that is $0$.