Questions tagged [reduced-residue-system]
52 questions
6
votes
2 answers
Sum of residue systems is complete iff they are both complete
Let $p$ and $q$ be distinct prime numbers. The integers $a_1, \ldots, a_p$ and $b_1,\ldots,b_q$ are such that the sums $a_i + b_j$ form a complete residue system modulo $pq$ (that is, there is precisely one sum which is $0$ mod $pq$, precisely one…
DesmondMiles
- 2,669
- 9
- 23
6
votes
0 answers
Permutations of $\{1,\ldots,2pq\}$ modulo $2pq$
I am proposing here a variant of this problem.
Let $p$ and $q$ be distinct odd primes. Is it true that there exists a permutation $\sigma$ of $\{1,\ldots,2pq\}\times \{1,2\}$ such…
Paolo Leonetti
- 15,021
- 3
- 23
- 57
4
votes
1 answer
$\{r_1,r_2,...,r_{\phi(m)}\}$ is a reduced residue system modulo $m$ iff $\{r_1+k,r_2+k,...,r_{\phi(m)}+k\}$ be a reduced residue system modulo $m$
Let $2\lt m\in \mathbb N$ and $\{r_1,r_2,...,r_{\phi(m)}\}$ be a reduced residue system modulo $m$. I want to find a necessary and sufficient condition for $k$ such that the set $\{r_1+k,r_2+k,...,r_{\phi(m)}+k\}$ be a reduced residue system modulo…
hamid kamali
- 3,181
- 13
- 25
4
votes
0 answers
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 number of elements in a reduced residue system…
Larry Freeman
- 10,301
- 4
- 22
- 56
3
votes
1 answer
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$ is $\{1,2,3,4\}$
These divide evenly into…
Larry Freeman
- 10,301
- 4
- 22
- 56
3
votes
1 answer
Estimating the number of elements with a given least prime factor in a sequence of consecutive integers
Let $a,n$ be any positive integers.
Let $\varphi(x)$ be the Euler totient function.
It seems to me that the number of elements $x$ with $a \le x < a+n$ that have a given least prime factor will be less than each of the following…
Larry Freeman
- 10,301
- 4
- 22
- 56
3
votes
0 answers
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\#}\right| =…
Larry Freeman
- 10,301
- 4
- 22
- 56
2
votes
1 answer
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.
Colin Defant
- 1,267
- 6
- 15
2
votes
1 answer
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 generate $4$ of the elements of the reduced residue…
Larry Freeman
- 10,301
- 4
- 22
- 56
2
votes
0 answers
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 primorial $5\# = 30$
The reduced residue class is…
Larry Freeman
- 10,301
- 4
- 22
- 56
2
votes
0 answers
Primes in reduced residue systems
I am trying to prove the following conjecture:
Let it be $R_m(n) / m>0, m\in \Bbb N$ some reduced residue system modulo $n$ such that $R_m(n)$ is the reduced residue system between $(m-1)n$ and $mn$, and such that some element of the reduced residue…
Juan Moreno
- 831
- 8
- 15
2
votes
1 answer
We have $a^{n-1} \equiv 1\ (mod\ n)$ but $a^{m} \not\equiv 1\ (mod\ n)$ for every divisor $m$ of $n - 1$, other than itself. Prove that $n$ is prime.
The integers $a$ and $n > 1$ satisfy $a^{n-1} \equiv 1\ (mod\ n)$ but $a^{m} \not\equiv 1\ (mod\ n)$ for every divisor $m$ of $n - 1$, other than itself. Prove that $n$ is prime.
The way I went about proving it was,
We know for every integer $k…
SS'
- 1,138
- 1
- 15
- 26
2
votes
2 answers
Show that the $k^\text{th}$ powers of a reduced residue system form a reduced residue system if and only if $(k, \phi(m)) = 1$.
Let $r_1,r_2,\ldots, r_n$ be a reduced residue system modulo $m$, where $n = \phi(m)$. Show that the numbers $r_1^k,r_2^k,\ldots,r_n^k$ form a reduced residue system modulo $m$ if and only if $(k, \phi(m)) = 1$.
I am supposed to make use of the…
b_pcakes
- 1,453
- 13
- 28
2
votes
1 answer
If $p$ is an odd prime and $p \nmid a$, show that $a^{(p-1)/2} \equiv \pm 1 \pmod {p}$
If $p$ is an odd prime and $p \nmid a$, show that $a^{(p-1)/2} \equiv \pm 1 \pmod{p}$.
So I can completely see Fermat's Little Theorem in this problem, in class we went over the theorem as well as an alternate version which states $a^p \equiv a…
Nick Powers
- 955
- 11
- 23
2
votes
0 answers
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 of
the finite fields ${\bf Z}/q {\bf Z}$ where…
Larry Freeman
- 10,301
- 4
- 22
- 56