Sum of elements in reduced residue system modulo n is divisible by n [duplicate]
$begingroup$
This question already has an answer here:
Show that if $c_1, c_2, ldots, c_{phi(m)}$ is a reduced residue system modulo m, $m neq 2$ then $c_1 + cdots+ c_{phi(m)} equiv 0 pmod{m}$
3 answers
Prove that sum of elements in reduced residue system modulo $n in N$ is divisible by $n$.
I feel like problem just comes down to pairing elements of RRS in way that they are congruent, but can't quite work it out.
Please post detailed and readable answer, as most of problems I need to do basically comes down to this one ..
elementary-number-theory reduced-residue-system
$endgroup$
marked as duplicate by Brahadeesh, Lord Shark the Unknown, mrtaurho, KReiser, José Carlos Santos Dec 19 '18 at 8:12
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
|
show 2 more comments
$begingroup$
This question already has an answer here:
Show that if $c_1, c_2, ldots, c_{phi(m)}$ is a reduced residue system modulo m, $m neq 2$ then $c_1 + cdots+ c_{phi(m)} equiv 0 pmod{m}$
3 answers
Prove that sum of elements in reduced residue system modulo $n in N$ is divisible by $n$.
I feel like problem just comes down to pairing elements of RRS in way that they are congruent, but can't quite work it out.
Please post detailed and readable answer, as most of problems I need to do basically comes down to this one ..
elementary-number-theory reduced-residue-system
$endgroup$
marked as duplicate by Brahadeesh, Lord Shark the Unknown, mrtaurho, KReiser, José Carlos Santos Dec 19 '18 at 8:12
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
Not true for even $n$.
$endgroup$
– Robert Israel
Dec 18 '18 at 16:23
1
$begingroup$
Really ? What's your counterexample ?
$endgroup$
– user626177
Dec 18 '18 at 16:43
1
$begingroup$
@someone what about $2$?
$endgroup$
– Maged Saeed
Dec 18 '18 at 17:45
1
$begingroup$
@MagedSaeed Is it working for $n ne 2$ ?
$endgroup$
– user626177
Dec 18 '18 at 17:57
$begingroup$
@someone consider my answer for other values of $n$. :)
$endgroup$
– Maged Saeed
Dec 18 '18 at 18:19
|
show 2 more comments
$begingroup$
This question already has an answer here:
Show that if $c_1, c_2, ldots, c_{phi(m)}$ is a reduced residue system modulo m, $m neq 2$ then $c_1 + cdots+ c_{phi(m)} equiv 0 pmod{m}$
3 answers
Prove that sum of elements in reduced residue system modulo $n in N$ is divisible by $n$.
I feel like problem just comes down to pairing elements of RRS in way that they are congruent, but can't quite work it out.
Please post detailed and readable answer, as most of problems I need to do basically comes down to this one ..
elementary-number-theory reduced-residue-system
$endgroup$
This question already has an answer here:
Show that if $c_1, c_2, ldots, c_{phi(m)}$ is a reduced residue system modulo m, $m neq 2$ then $c_1 + cdots+ c_{phi(m)} equiv 0 pmod{m}$
3 answers
Prove that sum of elements in reduced residue system modulo $n in N$ is divisible by $n$.
I feel like problem just comes down to pairing elements of RRS in way that they are congruent, but can't quite work it out.
Please post detailed and readable answer, as most of problems I need to do basically comes down to this one ..
This question already has an answer here:
Show that if $c_1, c_2, ldots, c_{phi(m)}$ is a reduced residue system modulo m, $m neq 2$ then $c_1 + cdots+ c_{phi(m)} equiv 0 pmod{m}$
3 answers
elementary-number-theory reduced-residue-system
elementary-number-theory reduced-residue-system
asked Dec 18 '18 at 16:08
user626177
marked as duplicate by Brahadeesh, Lord Shark the Unknown, mrtaurho, KReiser, José Carlos Santos Dec 19 '18 at 8:12
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Brahadeesh, Lord Shark the Unknown, mrtaurho, KReiser, José Carlos Santos Dec 19 '18 at 8:12
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
Not true for even $n$.
$endgroup$
– Robert Israel
Dec 18 '18 at 16:23
1
$begingroup$
Really ? What's your counterexample ?
$endgroup$
– user626177
Dec 18 '18 at 16:43
1
$begingroup$
@someone what about $2$?
$endgroup$
– Maged Saeed
Dec 18 '18 at 17:45
1
$begingroup$
@MagedSaeed Is it working for $n ne 2$ ?
$endgroup$
– user626177
Dec 18 '18 at 17:57
$begingroup$
@someone consider my answer for other values of $n$. :)
$endgroup$
– Maged Saeed
Dec 18 '18 at 18:19
|
show 2 more comments
$begingroup$
Not true for even $n$.
$endgroup$
– Robert Israel
Dec 18 '18 at 16:23
1
$begingroup$
Really ? What's your counterexample ?
$endgroup$
– user626177
Dec 18 '18 at 16:43
1
$begingroup$
@someone what about $2$?
$endgroup$
– Maged Saeed
Dec 18 '18 at 17:45
1
$begingroup$
@MagedSaeed Is it working for $n ne 2$ ?
$endgroup$
– user626177
Dec 18 '18 at 17:57
$begingroup$
@someone consider my answer for other values of $n$. :)
$endgroup$
– Maged Saeed
Dec 18 '18 at 18:19
$begingroup$
Not true for even $n$.
$endgroup$
– Robert Israel
Dec 18 '18 at 16:23
$begingroup$
Not true for even $n$.
$endgroup$
– Robert Israel
Dec 18 '18 at 16:23
1
1
$begingroup$
Really ? What's your counterexample ?
$endgroup$
– user626177
Dec 18 '18 at 16:43
$begingroup$
Really ? What's your counterexample ?
$endgroup$
– user626177
Dec 18 '18 at 16:43
1
1
$begingroup$
@someone what about $2$?
$endgroup$
– Maged Saeed
Dec 18 '18 at 17:45
$begingroup$
@someone what about $2$?
$endgroup$
– Maged Saeed
Dec 18 '18 at 17:45
1
1
$begingroup$
@MagedSaeed Is it working for $n ne 2$ ?
$endgroup$
– user626177
Dec 18 '18 at 17:57
$begingroup$
@MagedSaeed Is it working for $n ne 2$ ?
$endgroup$
– user626177
Dec 18 '18 at 17:57
$begingroup$
@someone consider my answer for other values of $n$. :)
$endgroup$
– Maged Saeed
Dec 18 '18 at 18:19
$begingroup$
@someone consider my answer for other values of $n$. :)
$endgroup$
– Maged Saeed
Dec 18 '18 at 18:19
|
show 2 more comments
1 Answer
1
active
oldest
votes
$begingroup$
The reduced residue system of $2$ is only $1$. But $2not | 1$, so, $n > 2$.
Let us address this problem for numbers greater than $2$. Now, since $gcd(a,n) = 1$, what can you say about $gcd(n-a,n)$? It is also $1$. Now, we can use this to pair elements of the Reduced Residue System, as you have suggested, as follows:
$a_1+a_2+a_3+cdots+a_{phi(n)over2}+(n-a_1)+(n-a_2)+cdots+(n-a_{phi(n)over2}) = frac{phi(n)}{2}n$. This also can give you a hint why $2$ is a counter example as $phi(n)$ is only odd for $n=2$. This answer is collected from answers in this post.
answered Dec 18 '18 at 18:18
Maged SaeedMaged Saeed
8771417
$endgroup$
1
$begingroup$
Ooh, right .. So if $k in RRS$ then $n-k in RRS$ because $(n-k, n) = 1$ and $n-k ne k mod n$ ?
$endgroup$
– user626177
Dec 18 '18 at 18:32
1
$begingroup$
Yeah, you got it.
$endgroup$
– Maged Saeed
Dec 18 '18 at 18:37
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The reduced residue system of $2$ is only $1$. But $2not | 1$, so, $n > 2$.
Let us address this problem for numbers greater than $2$. Now, since $gcd(a,n) = 1$, what can you say about $gcd(n-a,n)$? It is also $1$. Now, we can use this to pair elements of the Reduced Residue System, as you have suggested, as follows:
$a_1+a_2+a_3+cdots+a_{phi(n)over2}+(n-a_1)+(n-a_2)+cdots+(n-a_{phi(n)over2}) = frac{phi(n)}{2}n$. This also can give you a hint why $2$ is a counter example as $phi(n)$ is only odd for $n=2$. This answer is collected from answers in this post.
answered Dec 18 '18 at 18:18
Maged SaeedMaged Saeed
8771417
$endgroup$
1
$begingroup$
Ooh, right .. So if $k in RRS$ then $n-k in RRS$ because $(n-k, n) = 1$ and $n-k ne k mod n$ ?
$endgroup$
– user626177
Dec 18 '18 at 18:32
1
$begingroup$
Yeah, you got it.
$endgroup$
– Maged Saeed
Dec 18 '18 at 18:37
add a comment |
$begingroup$
The reduced residue system of $2$ is only $1$. But $2not | 1$, so, $n > 2$.
Let us address this problem for numbers greater than $2$. Now, since $gcd(a,n) = 1$, what can you say about $gcd(n-a,n)$? It is also $1$. Now, we can use this to pair elements of the Reduced Residue System, as you have suggested, as follows:
$a_1+a_2+a_3+cdots+a_{phi(n)over2}+(n-a_1)+(n-a_2)+cdots+(n-a_{phi(n)over2}) = frac{phi(n)}{2}n$. This also can give you a hint why $2$ is a counter example as $phi(n)$ is only odd for $n=2$. This answer is collected from answers in this post.
answered Dec 18 '18 at 18:18
Maged SaeedMaged Saeed
8771417
$endgroup$
1
$begingroup$
Ooh, right .. So if $k in RRS$ then $n-k in RRS$ because $(n-k, n) = 1$ and $n-k ne k mod n$ ?
$endgroup$
– user626177
Dec 18 '18 at 18:32
1
$begingroup$
Yeah, you got it.
$endgroup$
– Maged Saeed
Dec 18 '18 at 18:37
add a comment |
$begingroup$
The reduced residue system of $2$ is only $1$. But $2not | 1$, so, $n > 2$.
Let us address this problem for numbers greater than $2$. Now, since $gcd(a,n) = 1$, what can you say about $gcd(n-a,n)$? It is also $1$. Now, we can use this to pair elements of the Reduced Residue System, as you have suggested, as follows:
$a_1+a_2+a_3+cdots+a_{phi(n)over2}+(n-a_1)+(n-a_2)+cdots+(n-a_{phi(n)over2}) = frac{phi(n)}{2}n$. This also can give you a hint why $2$ is a counter example as $phi(n)$ is only odd for $n=2$. This answer is collected from answers in this post.
answered Dec 18 '18 at 18:18
Maged SaeedMaged Saeed
8771417
$endgroup$
The reduced residue system of $2$ is only $1$. But $2not | 1$, so, $n > 2$.
Let us address this problem for numbers greater than $2$. Now, since $gcd(a,n) = 1$, what can you say about $gcd(n-a,n)$? It is also $1$. Now, we can use this to pair elements of the Reduced Residue System, as you have suggested, as follows:
$a_1+a_2+a_3+cdots+a_{phi(n)over2}+(n-a_1)+(n-a_2)+cdots+(n-a_{phi(n)over2}) = frac{phi(n)}{2}n$. This also can give you a hint why $2$ is a counter example as $phi(n)$ is only odd for $n=2$. This answer is collected from answers in this post.
answered Dec 18 '18 at 18:18
Maged SaeedMaged Saeed
8771417
answered Dec 18 '18 at 18:18
Maged SaeedMaged Saeed
8771417
answered Dec 18 '18 at 18:18
Maged SaeedMaged Saeed
8771417
answered Dec 18 '18 at 18:18
Maged SaeedMaged Saeed
8771417
8771417
1
$begingroup$
Ooh, right .. So if $k in RRS$ then $n-k in RRS$ because $(n-k, n) = 1$ and $n-k ne k mod n$ ?
$endgroup$
– user626177
Dec 18 '18 at 18:32
1
$begingroup$
Yeah, you got it.
$endgroup$
– Maged Saeed
Dec 18 '18 at 18:37
add a comment |
1
$begingroup$
Ooh, right .. So if $k in RRS$ then $n-k in RRS$ because $(n-k, n) = 1$ and $n-k ne k mod n$ ?
$endgroup$
– user626177
Dec 18 '18 at 18:32
1
$begingroup$
Yeah, you got it.
$endgroup$
– Maged Saeed
Dec 18 '18 at 18:37
1
1
$begingroup$
Ooh, right .. So if $k in RRS$ then $n-k in RRS$ because $(n-k, n) = 1$ and $n-k ne k mod n$ ?
$endgroup$
– user626177
Dec 18 '18 at 18:32
$begingroup$
Ooh, right .. So if $k in RRS$ then $n-k in RRS$ because $(n-k, n) = 1$ and $n-k ne k mod n$ ?
$endgroup$
– user626177
Dec 18 '18 at 18:32
1
1
$begingroup$
Yeah, you got it.
$endgroup$
– Maged Saeed
Dec 18 '18 at 18:37
$begingroup$
Yeah, you got it.
$endgroup$
– Maged Saeed
Dec 18 '18 at 18:37
add a comment |
$begingroup$
Not true for even $n$.
$endgroup$
– Robert Israel
Dec 18 '18 at 16:23
1
$begingroup$
Really ? What's your counterexample ?
$endgroup$
– user626177
Dec 18 '18 at 16:43
1
$begingroup$
@someone what about $2$?
$endgroup$
– Maged Saeed
Dec 18 '18 at 17:45
1
$begingroup$
@MagedSaeed Is it working for $n ne 2$ ?
$endgroup$
– user626177
Dec 18 '18 at 17:57
$begingroup$
@someone consider my answer for other values of $n$. :)
$endgroup$
– Maged Saeed
Dec 18 '18 at 18:19