# Questions tagged [reduced-residue-system]

The tag has no usage guidance.

41 questions
Filter by
Sorted by
Tagged with
81 views

### Proof of infinitude of primes using ratio of n to its totient

A few preliminaries: A primorial is the product of the first primes. There are two notations for this ($n\#$ is the product of all primes under $n$, and $p_n\#$ is the product of the first $n$ primes;...
29 views

### Regarding proving a result related to complete residue system which is to be used in proving multiplicative property of Hecke Operators

I am self studying analytic number theory from Tom M apostol and couldn't think about how apostol proves a result related to complete residue systems. The original theorem in which deduction appears ...
31 views

250 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 ...
76 views

68 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 ...
35 views

107 views

533 views

### How is $3$ not a primitive root mod 8?

Sources are telling me that there are no primitive roots $\mod 8$, yet $\phi (8) = 4$ and $3^{\phi(8)} = 1 \mod 8$. Thus $1, 3$ form a reduced residue system.
70 views

### Question about the Chinese Remainder Theorem and the residue class ring ${\bf Z}/p\# {\bf Z}$

In a question that I asked on MO, Terence Tao observed that: The Chinese Remainder Theorem tells us that the residue class ring ${\bf Z}/p\# {\bf Z}$ is isomorphic (as a ring) to the product of ...
261 views

### Question about the elements of a reduced residue system relative a primorial $p_n\#$

I've been dividing up the elements of reduced residue system relative a prime $p_n$ into congruence classes modulo $p_{n+1}$ and I noticed that each congruence class is represented. If $r$ = the ...
97 views

### Reasoning about the number of elements in a reduced residue system relative a primorial

Let $R_{p_i\#}$ be the reduced residue system relative the primorial for the $i$th prime. Let $\left|R_{p_i\#}\right|$ be the number of elements in this set. It is well known that: \left|R_{p_i\#}...
139 views

### Reduced Residue System in Mathematica

How can I create the standard reduced residue system modulo $m$ in Mathematica for a given positive integer $m$? For example, if I input $10$, I would like it to give me the list $\{1,3,7,9\}$. Thanks....
163 views

### Reduced residue systems and prime k-tuple bijection

First off, the terminology: Primorials: the products of the first $n$ primes, written as $P_n \#$. Reduced residue system modulo a positive integer $K$: Those numbers smaller than $K$ that are ...
155 views

### Infinite “Twins” in reduced residue systems modulo primorials

The Lth primorial ($p_L\#$) is the product of the first L prime numbers. The reduced residue system modulo $p_L\#$ is any set of positive integers with cardinality equal to the totient of $p_L\#$ ...
332 views

### Question about congruence classes and reduced residue systems

Let $x$,$y$ be integers such that the reduced residue system modulo $y$ divides equally into congruence classes modulo $x$. An example of this is $x=4$, $y=5$. The reduced residue system modulo $5$ ...
60 views

### Solving for $x$ where $p^x \equiv 1 \pmod {q\#}$

For a given primorial $q\#$, you can generate a subset of the reduced residue system by using the power of a prime $p$ where $p > q$. For example, for $5\#$, we can use the powers of $7$ to ...
60 views

### Can all elements of a reduced residue class of a primorial $p$ be expressed as a simple equation in terms of the factors of the primorial?

I've noticed that for the smaller primes, it is possible to state each element of its reduced residue class as a simple equation in terms of the factors of the primorial. For example, consider the ...
Let $R_{p_k\#}$ be the set of elements in the reduced residue system modulo $p_k\#$. Let $|R_{p_k\#}|$ be the number of elements in this set. If $p_i < p_k$ and $p_i$ divides $|R_{p_k\#}|$, does ...
It is well known that the number of elements in the reduced residue system for a given primorial $p_k\#$ is divisible by $p_k - 1$. Does it follow that if you divide the elements of a reduced residue ...