Questions tagged [chinese-remainder-theorem]
For questions related to the Chinese Remainder Theorem and its applications.
905
questions
-1
votes
0
answers
52
views
Are there infinitely many primes p for which either $p−1$ or $p+1$ is squarefree?" [duplicate]
It is not known if there is an infinite number of primorial primes.
Are there infinitely many primes $p$ for which either $p−1$ or $p+1$ is
squarefree?"
I imagine this is an open problem also,...
- 20.7k
2
votes
0
answers
82
views
Homology + Chinese Remainder Theorem =?
Let $M_i, i=1..n$ be a finite collection of pair-wise coprime moduli. The Chinese remainder theorem says that $\Bbb{Z}/M \approx \prod_i \Bbb{Z}/M_i$. Without going into Bezout / Euclidean algorithm,...
1
vote
3
answers
48
views
Question about Existence Proof for Chinese Remainder Theorem Using Mapping
I'm confused about a proof of existence for the Chinese Remainder Theorem:
If the $n_i$ are pairwise coprime, and if $a_1, a_2, \ldots, a_k$ are any integers, then the system
$$
\begin{align}
x &\...
- 53
2
votes
2
answers
85
views
In polynomial quotient rings over $\mathbb{F}_2$, how to use Chinese Remainder Theorem to solve equations?
Suppose I work over the polynomial quotient ring $\mathbb{F}_2[x,y]/\langle x^m+1,y^n+1\rangle$, and I want to solve for polynomials $s[x,y]$ that simultaneously solve the equations
\begin{equation}
a[...
- 133
2
votes
1
answer
61
views
Period of binary sequences [closed]
Let $k>0$ be an integer. Consider a finite binary sequence $\sigma=(b_0,b_1,...,b_{n-1})$ where $n=2\cdot 3 \cdots p_k $ is the product of the first $k$ primes, and $b_i=1$ iff $i$ is divisible by ...
- 133
0
votes
0
answers
35
views
Intuition behind terms in Chinese Remainder Theorem solution formula [duplicate]
Given the following equations: $$ a = 2 \ (mod \ 5)$$ and $$ a = 3 \ (mod \ 13)$$
Let $a_1=2$, $a_2=3$, $n_1=5$, $n_2=13$, $m_1=13$, $m_2=5$
Let $m=5 \times 13=65$
Let $$c_i = m_i * (m^{-1}_i mod \ ...
- 81
1
vote
2
answers
50
views
Question over decomposition of $\mathbb{Z}_{mn}$
If $m<n\in\mathbb{N}$ and $(m,n)=1$, then there is a natural isomorphism $h: \mathbb{Z}_{mn}\to \mathbb{Z}_m \times \mathbb{Z}_n$. But I'm a little confused about what happens when multiplying $m$ ...
- 1,670
-1
votes
1
answer
68
views
Modular Solution to $x^2\equiv2 \pmod{2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 19 \cdot 23}$ [duplicate]
How many solutions are there to $x^2\equiv2 \pmod{2 \cdot 3 \cdot 5
\cdot 7 \cdot 11 \cdot 19 \cdot 23}$
Is it enough to say by Chinese Remainder Theorem, there must be solutions for all individual ...
- 794
0
votes
0
answers
41
views
Find the least number that obtained when divided by $A$ and $B$ leaves the remainder $a$ and $b$ respectively. Also $A-a=B-b=d$. [duplicate]
Find the least number that obtained when divided by $A$ and $B$ leaves the remainder $a$ and $b$ respectively. Also $A-a=B-b=d.$
My attempt
Answer given is $LCM(A,B)-d.$
I tried to prove using the ...
- 849
0
votes
1
answer
62
views
How to show that gcd of two quasiperiods is a quasiperiod?
Definition 3.1.1 in page 25 of this book is the definition of quasiperod and Proposition 3.1.3. shows that gcd of two quasiperiods is a quasiperiod. The whole proof is clear except for the part about ...
- 281
2
votes
0
answers
37
views
If $x\equiv0\pmod a$ and $x\equiv k\pmod b$, is there a simple expression for $x \pmod {ab}$? [duplicate]
Suppose I know that for some values $x,a,b$ that
$$
x \equiv 0\pmod a
$$
$$
x \equiv k\pmod b.
$$
Is there a simple expression that I can use to get the value of $x$ $\pmod{ab}$ assuming that $a,b$ ...
- 3,105
4
votes
0
answers
99
views
Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is divisible by at least one prime number less than $n$
As a continuation of this question relating the Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is composite and this other one on the divisibility of numbers in intervals ...
- 1,190
-1
votes
1
answer
84
views
Why must the order of $7$ either be $5$ or $10$ in $\mathbb{Z}_{11}^*$? [closed]
I have an old math exam question with the solution included, but there is a certain step of the solution I don't understand.
Task: Determine the order of $7$ in $\mathbb{Z}_{44}^*$
Solution: From the ...
- 317
3
votes
1
answer
122
views
Given a tuple of $k$ distinct integers, is there a generator list in a $\mathbb{Z}/n\mathbb{Z}$ that matches the tuple?
Motivation: In $\langle\mathbb{Z}/7\mathbb{Z},\times\rangle,\ \langle 3\rangle = (3,2,6,4,5,1).$
Given a $k-$tuple of distinct integers, $q_1, q_2, \ldots, q_k,$ (all
nonzero) does $\exists$ integers ...
- 20.7k
0
votes
0
answers
37
views
Stationary sequence of orders in $(\mathbb{Z}/p^n\mathbb{Z})^\ast$
I am struggling to prove the following statement:
Let $p, q$ be coprime numbers. For all $n \in \mathbb{N}^*$, we define $t_n$ as the order of $[q]$ in $(\mathbb{Z}/{p^n}\mathbb{Z})^\ast$.
Show that $(...
- 345