Linked Questions

1
vote
1answer
212 views

Sum of elements in reduced residue system modulo n is divisible by n [duplicate]

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 ...
0
votes
2answers
62 views

If $m > 0$, fix a reduced residue system $r_{1}, r_2, \dotsc, r_{\varphi(m)} $ mod $ m$. Let $x=r_1+r_2+\dotsb+r_{\varphi(m)}$. What is $x$ mod $m$? [duplicate]

Given $m > 0$, fix a reduced residue system (RRS) $r_{1}, r_2,\dotsc , r_{\varphi(m)} $ mod $ m$. Let $x$ denote the sum $r_1 + r_2 + \dotsb + r_{\varphi(m)}$. What is $x$ mod $m$? The problem is ...
32
votes
7answers
17k views

Why is Euler's Totient function always even?

I want to prove why $\phi(n)$ is even for $n>3$. So far I am attempting to split this into 2 cases. Case 1: $n$ is a power of $2$. Hence $n=2^k$. So $\phi(n)=2^k-2^{k-1}$. Clearly that will ...
30
votes
7answers
7k views

Product of all elements in an odd finite abelian group is 1

This should be an easy exercise: Given a finite odd abelian group $G$, prove that $\prod_{g\in G}g=e$. Indeed, using Lagrange's theorem this is trivial: There is no element of order 2 (since the order ...
2
votes
4answers
550 views

Why is sum of a sequence $\displaystyle s_n = \frac{n}{2}(a_1+a_n)$?

Is there a way to prove that the sum of the arithmetic progression $a_1, a_2, \dots, a_n$ can be calculated by $\displaystyle s_n = \frac{n}{2}(a_1+a_n)$?
5
votes
4answers
1k views

Prove that the product of coprimes must be congruent to $-1$ or $1 \pmod{m}$

I can't figure this problem out. Let $b_1, b_2, \cdots, b_{\phi(m)}$ be the integers between $1$ and $m$ that are relatively prime to $m$. $B$ is the product of these integers. Prove that either $B$ ...
2
votes
4answers
2k views

Prove that, for any set of consecutive integers with an odd number of terms, the sum of the integers is always a multiple of the number of terms.

For example, the sum of 1, 2, and 3 (three consecutives -- an odd number) is 6, which is a multiple of 3.
3
votes
3answers
699 views

Prove the sum of all numbers that do not have a multiplicative inverse mod $n$

I understand that for a number $a$ to have a multiplicative inverse in mod $n$, it must be coprime to $n$; therefore, all numbers that do not have a multiplicative inverse mod $n$ must share a factor ...
0
votes
2answers
200 views

Prove that if $n>1$, the sum of positive integers less than $n$ and coprime to $n$ is $(1/2)na(n)$ where $a(n)$ is the number of such integers. [duplicate]

Question 12(iii) Could anyone explain this part of the question to me. What i tried co-prime means that the two integers a and b are said to be relatively prime, mutually prime, or coprime (also ...
1
vote
2answers
77 views

A base in which all primes end with $5$ different symbols?

In base $10$, all prime numbers (a part $2$ and $5$) end with $1,3,7$ or $9$, i.e. with four different symbols. Is there a base in which all prime numbers end with $5$ different symbols (or also with ...