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

Unread post by Arif Ahmed » Thu May 24, 2012 10:15 pm

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$

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

Re: finding reduced residue system

Unread post by SANZEED » Sat May 26, 2012 6:14 pm

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

Unread post by shehab ahmed » Sat May 26, 2012 8:26 pm

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

Unread post by Arif Ahmed » Sun May 27, 2012 11:32 am

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.

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

Re: finding reduced residue system

Unread post by Phlembac Adib Hasan » Sun May 27, 2012 4:37 pm

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? :lol:
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 8-) )
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

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

Re: finding reduced residue system

Unread post by SANZEED » Mon May 28, 2012 1:01 am

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!}}$

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

Re: finding reduced residue system

Unread post by *Mahi* » Mon May 28, 2012 1:16 am

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

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

Re: finding reduced residue system

Unread post by Phlembac Adib Hasan » Mon May 28, 2012 7:58 am

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

Unread post by shehab ahmed » Mon May 28, 2012 10:56 pm

আমার সলিউশনটা কেউ দেখ।আমি শিওর এখানে কোথাও না কোথাও ভুল আছে
first let, $(n,\varphi (m))=1$ and $p$ be any prime factor of $m$ and $p^a||m$
we are given that all $a_i$'s are incongruent and co-prime to $m$.
Now,for sake of argument, let $a_i^n$ and $a_j^n$ are congruemt modulo $m$ that is modulo $p^a$.let, $g$ is a primitive root of $p^a$.
let, $a_i=g^m$ and $a_j=g^k$
it implies that $mn\equiv kn\pmod {\varphi p^a}$. Now, $(n,\varphi (p^a))=1$ so $m\equiv k \pmod \varphi (p^a)$. As $p$ can be any prime factor of $m$,continuing this argument for every prime factor $p$ of $m$,we can deduce that $a_i\equiv a_j\pmod m$ which is absurd.
For the converse, I have also used contradiction. Let, $(n,\varphi (m))>1$ so there is a prime $p$ such that $p^a||m$ and $(n,\varphi (p^a))>1$ consider that prime. By our assumption, $a_i^n$ is congruent to a unique $a_j\pmod m$ that is $\pmod p^a$.so $mn\equiv k\pmod\varphi (p^a)$. Let $d$ be a common prime divisor of $p^a$ and $n$. Then, $d|k$,but we have the freedom to choose $k$ such that $d$ is co prime to $k$ and the result follows from here
Last edited by Masum on Tue May 29, 2012 12:19 pm, edited 1 time in total.
Reason: LaTeXed

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

Re: finding reduced residue system

Unread post by Masum » Tue May 29, 2012 12:22 pm

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

Post Reply