finding reduced residue system
-
- Posts:10
- Joined:Tue Mar 15, 2011 10:39 am
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$
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?
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!}}$
-
- 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
-
- 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
What have you proved?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?
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
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!}}$
Re: finding reduced residue system
That is already given.SANZEED wrote:Sorry, but actually I wanted to show that $S_{0}$ is a reduced system,not $S$. Now what will you say?
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
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
Same question as Mahi vaia.Please read what I wrote before: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
-
- 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
Reason: LaTeXed
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$.