Questions tagged [reduced-residue-system]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
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;...
1
vote
1answer
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 ...
-1
votes
1answer
31 views

This should be a reduced residue system rather than a complete residue system, right?

In my lecture notes there is a lemma which states the following : Suppose $a_1,....a_{\phi(n)}$ is a complete set of residues , coprime to $n$, if $k \in \Bbb N, s.t.(k,n)=1$, then $ka_1, ka_2, ….,...
1
vote
0answers
47 views

Does the Sylvester-Schur theorem apply to complete residue systems?

Let $p_k$ be the $k$th prime. If $k \ge 3$, the following sequence forms a complete residue system modulo $p_k$: $$3(1)+1, 3(2)+1, 3(3)+1, \dots, 3(p_k)+1$$ If $k=3, p_3=5$, $7 = 3(2)+1$ If $k=4, ...
1
vote
1answer
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 ...
2
votes
0answers
76 views

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 $...
1
vote
0answers
38 views

Prove that the there exists a single Reduced residue system.

Let $m$ and $n$ be two integers such that $(m, n) = 1$ and $\phi(m) =\phi(n) $. Then there exists a single residue system which is congruent both modulo $m$ as well as $n$. What i know is that if $(m,...
0
votes
2answers
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 ...
0
votes
2answers
35 views

Reducing the result of $z=e^{x^2-y^2}\cos(2xy)$ after a coordinate rotation by $45^\circ$

Starting with $$z=e^{x^2-y^2}\cos(2xy)$$ I must make the substitution $$\begin{align} x &\to \phantom{-} x\cos 45^\circ + y\sin 45^\circ \\ y &\to -x\sin 45^\circ + y \cos 45^\circ \end{align}...
2
votes
1answer
56 views

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

easy number theory: Given n and m are coprime, should $\text{lcm}(φ(m),φ(n)) = φ(m) \times φ(n)$ [closed]

Given two positive integer $n$ and $m$ are coprime, show that $\text{lcm}( φ(m), φ(n) ) = φ(m) \times φ(n)$
0
votes
0answers
113 views

Reduced Residue System Proof

Prove that if $$r_1,r_2,...,r_{\phi(m)}$$ is a reduced residue system modulo $m$, and $m$ is odd, then $$m|r_1+r_2+...+r_{\phi(m)}$$ My attempt at proof was to first prove that for any two ...
0
votes
1answer
625 views

Wilson Theorem to find least nonnegative residue modulo m

I want to know how can we use Wilson's theorem to find least nonnegative residue modulo $m$. For example: $$n = 64! \quad m = 67$$ Can you please explain the process step by step? Thank you
0
votes
0answers
793 views

finding the least nonnegative residue

I do not really understand how to find the least non negative residue for an integer n mod m. Can you anyone explain to me with an example how to do it?
1
vote
2answers
465 views

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, \...
0
votes
2answers
511 views

What is meant by residue system and residue class in modular arithmetic?

From surfing the net I got to knew that residue class is something related to the set {0,1,....,n-1} for a number n. Similar thing is about residue system. So, can you help me a little to clear the ...
6
votes
0answers
130 views

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 that $$ \{\sigma(1,...
1
vote
1answer
107 views

Invariance of residues modulo $p$

Let $p$ be an odd prime. Is it true that there exists a permutation $\sigma$ of the set $$ \{1,\ldots,2p-1\}\setminus \{p\} $$ such that $$ \{\sigma(1),\ldots,(p-1)\sigma(p-1)\}=\{\sigma(p+1),\ldots,(...
0
votes
1answer
29 views

Let $k, p, q$ be distinct primes. How to determine unique $n \in \{q, q + k, q + 2k, \ldots, q + (p - 1)k\}$ such that $\gcd(n, p) \gt 1$

Given the distinct primes $k, p, q$, is there a formula or algorithm to obtain the unique $n \in \{q, q + k, q + 2k, \ldots, q + (p - 1)k\}$ such that $\gcd(n, p) \gt 1$?
1
vote
2answers
36 views

Let $q$, $p$ be distinct primes. Determine unique $n$ in $\{q, q+1, \ldots, q+p-1\}$ such that $\gcd(p, n) > 1$

Is there a way to determine, given distinct primes $q, p$, the unique $n \in \{q, q+1, \ldots, q+p-1\}$ such that $\gcd(n, p) \gt 1$?
0
votes
1answer
588 views

Reduced residue system from complete residue system

Where can I read a proof of the following result? Online or textbook preferably. If $\Gamma = \{a_1, a_2, \ldots, a_m\}$ is a complete residue system modulo $m$, then $\{a_i \in \Gamma| g.c.d.(a_i, m)...
0
votes
1answer
40 views

Confusion in reduced residue systems

1 and 5 constitue a reduced residue system (mod 6). The book says a set of integers $a_1,...,a_h$ is a reduced residue system if it's incongruent (mod m) and relatively prime to m, such that if a is ...
0
votes
0answers
34 views

Application of Reduced residue system and modular

What i have done is that : a)when p is 3k+1, the number of elements of S : 3k and b)when p is 3k+2, the number of elements of S : 3k+1, a)the number of elements of A is $3k$ because each one in ...
2
votes
1answer
70 views

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 ...
0
votes
1answer
126 views

Show that the numbers $3$,$3^2$,$3^3$,$3^4$,$3^5$,$3^6$ for a reduced residue system modulo 7.

Show that the numbers $3$,$3^2$,$3^3$,$3^4$,$3^5$,$3^6$ for a reduced residue system modulo 7. -A bit lost with this question, we just started a section on reduced residue sets and only covered ...
0
votes
0answers
83 views

Is the set of reduced Residues the same as the set of units?

I am struggling with the concept of Units and the Reduced set of residues. I know that a unit is defined to be an element $(a)$ s.t there exists and inverse element $\hat{a}$. where $\hat{a} * a = 1$....
3
votes
1answer
335 views

$\{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_{\...
2
votes
0answers
63 views

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 ...
1
vote
1answer
44 views

Counting the number of integers $x$ in a sequence of $30a$ consecutive integers where $\gcd(x(x+2),30)=1$ and $p \mid x(x+2)$ where $p \ge 7$

I was writing a computer program and I found that for all sequences that I tested the number of $x$ in a sequence of $30a$ consecutive integers for a prime $p$ is less than or equal to: $$2\left\lceil\...
1
vote
4answers
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.
2
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
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\#}...
1
vote
1answer
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....
0
votes
1answer
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 ...
0
votes
1answer
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\#$ ...
2
votes
0answers
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$ ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
2answers
243 views

Distribution of a reduced residue system within a primorial

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 ...
0
votes
1answer
206 views

Question about the reduced residue system for a given primorial

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 ...