Questions tagged [chinese-remainder-theorem]
For questions related to the Chinese Remainder Theorem and its applications.
862
questions
2
votes
3
answers
89
views
Number of solutions of $y^2=x^3$ in $\mathbb{Z}_{57}$
The title explains the question. It was one of the 25 questions of a 3 hour olympiad, so I hope it is not too hard. The olympiad is for undergraduate students, so I also hope it doesn't use any "...
3
votes
1
answer
92
views
Deriving a CRT formula for noncoprime moduli
The German Wikipedia page on the Chinese Remainder Theorem states the following
Given are the two simultaneous congruences:
$$
\begin{aligned}
& x \equiv a \quad(\bmod n) \\
& x \equiv b \...
0
votes
0
answers
54
views
Find the remainder without differentiation [duplicate]
The degree of $f(x)$ is not given.
When $f(x)$ is divided by $(x-3)$ the remainder is $15$ and when $f(x)$ is divided by $(x-1)^2$ the remainder is $2x+1$.
Now we need to find the remainder when $f(x)$...
- 5,952
-1
votes
1
answer
39
views
Remainder of a product of numbers
When the positive integer N is divided by 6, the remainder is 3. When the positive integer M is divided by 4, the remainder is 1. Which of the following integers could be the remainder when the ...
- 1
2
votes
1
answer
71
views
How to find unique least number of moduli when performing arithmetic addition of two integers using Chinese Remainder theorem?
Here's my problem.
I have to find the sum of 123456 and 987456 using chinese remainder theorem with least moduli.
We know sum = 123456+987456=1,110,912.
Let me assume that we have to use n number of ...
0
votes
0
answers
29
views
Using Chinese remainder theorem for Gaussian integers
I have the following two questions that am trying to solve.
Use Chinese remainder theorem to solve this system of congruence
$x \equiv i \mod (1+i)$ and $x \equiv 2 \mod 3i$.
$x \equiv (−3+i) \mod ...
- 1
5
votes
1
answer
91
views
$9$ divides $a - 5$. $18$ divides $a - 14$. $24$ divides $a - 20$. Find $a$. [closed]
I find this tricky for some reason. Don't really know how to approach it. I found the answer, but it was by luck.
So first off, I write down:
$$a = 9x +5$$
$$a = 18y + 14$$
$$a = 24z +20$$
Not really ...
- 69
-1
votes
1
answer
74
views
A number when divided by 2,3,4,5,6 leaves remainder 1,2,3,4,5 respectively but when its divided by 11 the remainder is 0. FIND THE NUMBER [duplicate]
A number when divided by $2,3,4,5,6$ leaves remainder $1,2,3,4,5$ respectively but when its divided by $11$ the remainder is $0$. FIND THE NUMBER
I tried taking LCM of $2,3,4,5,6$ and subratcing by $1(...
- 15
0
votes
0
answers
39
views
Using Chinese Remainder theorem to find number of solutions of modular exponentiation mod composite number [duplicate]
I am struggling to understand a simple fact that should follow from the Chinese remainder theorem. Suppose we have a system of equations.
$$
x^n = 1 (mod\ p)
$$
$$
x^n = 1 (mod\ q)
$$
Where $p, q$ are ...
1
vote
0
answers
54
views
$X \equiv 1 \pmod{20} \land X \equiv 1 \pmod{22} \iff X \equiv 1 \pmod{\operatorname{lcm}(20,22)}$
$X \equiv 1 \pmod{20} \land X \equiv 1 \pmod{22} \iff X \equiv 1 \pmod{\operatorname{lcm}(20,22)}$
I dont understand how I would go about this proof. I am trying to use this to solve a CRT-problem ...
- 11
0
votes
2
answers
144
views
How can I show that: $x\equiv1\pmod{20}$ and $x\equiv1\pmod{22}$ iff $x\equiv1\pmod{220}$? [duplicate]
First off: I am completely new to modular arithmetic.
I am currently trying to solve the Problem:
$x \equiv3 \pmod{19}$
$x \equiv1 \pmod{20}$
$x \equiv2 \pmod{21}$
$x \equiv1 \pmod{22}$
$x \equiv0 \...
- 17
1
vote
1
answer
75
views
Nonconstant polynomial $f(x) \in \mathbb{Z}[x]$ with $f(0)=1$, then there exists an $n \in \mathbb{N}$ such that $f(n)$ is divisible by 2021 primes.
I'm working on a problem which is stated as follows :
Let $f(x) \in \mathbb{Z}[x]$ be a nonconstant polynomial with $f(0)=1$. Then, there exists $n \in \mathbb{N}$ such that $f(n)$ is divisible by $...
- 99
3
votes
1
answer
59
views
If $A\subset \mathbb{N}$ with $\vert A \vert = \infty,$ does $\exists p\in\mathbb{P}_{\geq 3}$ such that $\vert\{a\pmod p:a\in A\}\vert=p$ or $p-1?$
Let $\mathbb{P}$ be the set of prime numbers.
My original question was going to be this:
If $A\subset \mathbb{N}$ with $\ \vert A \vert = \infty,\ $ does $\ \exists\ p\in\mathbb{P} $ such
that $\ \...
- 17.8k
1
vote
1
answer
80
views
If $A$ is a Dedekind domain, and $\{0\} \ne I \vartriangleleft A$ is an ideal, then $A/I$ is a principal ideal ring
If $A$ is a Dedekind domain, and $\{0\} \ne I \vartriangleleft A$ is an ideal, then $A/I$ is a principal ideal ring.
I have questions about a proof of the said result here. I am reproducing the proof ...
- 13k
0
votes
1
answer
71
views
How do I find the cube root using the Extended Euclidean Algorithm? (RSA broadcast attack)
This is to solve for $m^3$ in an RSA broadcast attack where I have $c1$, $c2$, $c3$, $N1$, $N2$, $N3$ and $e=3$.
I use CRT (Chinese Remainder Theorem) to get $c1 \equiv c2 \equiv c3 \pmod {N_1 N_2 N_3}...
- 224
5
votes
2
answers
186
views
Proof of Chinese remainder theorem by isomorphism
My note states that we can prove Chinese remainder theorem as the way shown: Let $m$ and $n$ be coprime natural numbers. Then $C_{mn}$ is isomorphic to $C_m \times C_n$ (where $C_m$ is cyclic group ...
- 51
1
vote
0
answers
78
views
Prove that the direct limit has the universal property.
The Problem: Let $I$ be a nonempty index set with a partial order $\leq$. For each $i\in I$, let $A_i$ be an additive abelian group. Suppose for every $i, j\in I$ there is some $k\in I$ such that $k\...
- 1,179
0
votes
4
answers
143
views
$x \equiv 1 \pmod p$ and $x \equiv 1 \pmod q \Rightarrow x \equiv 1 \pmod {pq}$ proven in a certain way
Let $p$ and $q$ be two distinct odd prime numbers. Consider the following congruence equations:
$$x \equiv 1 \pmod{p}$$
$$x \equiv 1 \pmod{q}$$
It is obvious that $x \equiv 1 \pmod{pq}$. But I am ...
- 1,066
0
votes
0
answers
109
views
Solution of Chinese Remainder Theorem
The question is
Given that, x ≡ 6 (mod 11), x ≡ 13 (mod 16), x ≡ 9 (mod 21), x ≡ 19 (mod 25). Find x.
Using the Extended Euclidean Algorithm I computed the modular inverse ...
- 63
2
votes
1
answer
72
views
Isomorphism of Ring of real valued continuous functions on [0,1]
Let $R$ denotes the ring of real valued continuous functions on $[0,1]$. For each $x \in [0,1]$ we have $I_x=\{f\in R|f(x)=0 \}$ is a maximal ideal of $R$. I have seen the proof that $x\to I_x$ gives ...
- 265
0
votes
0
answers
13
views
Inverse chinese theorem $x \in Qr(n) \iff x \in Qr(p) \wedge x \in Qr( q)$ [duplicate]
I found this sentence in a paper :
Let $n=pq$ where $p, q$ are primes and let $Qr(n) = \{x^2 \mod n | \; x \in Z_n^*\}$ the set of quadratic residues in $Z^*_n$.
By Chinese remainder theorem we get :$$...
- 797
3
votes
1
answer
153
views
Integer GCD computation via Chinese Remainder Theorem
Is it possible to use Chinese Remainder Theorem to reconstruct the GCD of two integers from several GCDs of their modular representations (i.e. residues modulo pair-wise coprime integers)? For example:...
- 985
0
votes
2
answers
144
views
relationship between Chinese remainder theorem and roots of polynomials
According to https://eprint.iacr.org/2020/1481.pdf on page 9:
What is $\mathbb{Z}_p[\eta]$? I mean, $\eta := [X \mod F_1(X)]$. Does this mean a polynomial evaluated at $\eta$? If so, which polynomial?...
- 103
1
vote
1
answer
62
views
Proof of Kummer's Theorem in Janusz's Algebraic Number Fields
There is a theorem in Janusz's Algebraic Number Fields stated as follows:
Kummer's Theorem:
Let $R$ be a Dedekind ring with quotient field $K$ and $R'$ the integral closure of $R$ in a finite ...
- 27
4
votes
1
answer
107
views
Chinese remainder theorem for groups of matrices over rings
Let $N=p_1^{k_1}p_2^{k_2}$ and consider the group $GL_2(\mathbb{Z}/N\mathbb{Z})$.
I would like to use Chinese remainder map to show that the group is isomorphic to $GL_2(\mathbb{Z}/p_1^{k_1}\mathbb{Z})...
- 137
-1
votes
1
answer
51
views
If A is a number which divided by 7 give's remainder 1, divided by 9 remainder 1, divided by 64 remainder 3 and 35000<A<40000. Find A [closed]
If x is the number
x=7*p+1
x=9*q+1
x=64*r+3
From the first 2 equations is obvious that
x=63*s+1
The number is
556*63+1
.....
634*63+1
simultaneously has to be
547*64+3
...
624*64+3
My son wrote a 3 ...
0
votes
1
answer
38
views
Finding $|Aut(\mathbb{Z}_6 \times \mathbb{Z}_{10} \times \mathbb{Z}_{15})|$ [duplicate]
I am trying to compute:
$|Aut(\mathbb{Z}_6 \times \mathbb{Z}_{10} \times \mathbb{Z}_{15})|$
I know that:
If $H$ and $K$ have coprime orders then:
$Aut(K \times H) \cong Aut(K)\times Aut(H) $
For ...
- 1,639
1
vote
0
answers
86
views
$x^2 = 2044 \pmod{2408}$ find all the solutions
This is what I have so far:
I am stuck on how to solve $z^2 = 28 \pmod{56}$ I could continue to keep splitting it into primes but is there a method to find the solutions without a prime modulo?
2
votes
0
answers
60
views
Number Theory: What does $\theta_i$ mean here? [duplicate]
(Posting this again since the last one was an image and people told me to write it down).
Found this from this paper (Page 4; Section 4.1). Image version.
I wanted help in understand what $\theta_{i}$ ...
- 420
3
votes
0
answers
54
views
Minimum integer solution to some system of congruences involving prime numbers
Consider some system of congruences
$$
\left\{
\begin{aligned}
x &\equiv r_1 \pmod {p_1} \\
x &\equiv r_2 \pmod {p_2} \\
&\;\;\vdots \\
x &\equiv r_n \pmod{p_n}
\end{aligned}
\...
- 1,032
0
votes
0
answers
69
views
CRT and Evaluation
Given the quotient ring $\displaystyle R = \frac{\mathbb{Z}_q[x]}{\langle P(x)\rangle}$, for a prime $q$ and an irreducible polynomial $P(x)\in \mathbb{Z} [x]$. my question is there exist a $P,q$ and ...
- 191
2
votes
1
answer
73
views
Find the principal remainder of $\frac{431^5 + 611}{27}$
I have this problem: $\frac{431^5 + 611}{27}$
I'm supposed to find the principal remainder by hand. But I have no idea how to start when $431$ has en exponent of $5$. Can someone please explain? ...
- 381
1
vote
0
answers
159
views
A Chinese remainder theorem problem from 1997 slovak math olympiad
Doubt
I try to understand this question and solution . But i can not understand the red underlined section. Please can someone explain this solution .And what does it mean finately many prime . I know ...
- 415
3
votes
3
answers
156
views
Generate arbitrarily long sequences of consecutive numbers without primes.
Recently learned about this formula to generate consecutive composite numbers
$n!+2,n!+3,...,n!+n$
The goal of this question is to find if other methods exist to generate arbitrarily long sequences of ...
- 1,649
6
votes
2
answers
235
views
Find the last two non-zero digits of $70!$
The question itself is quite straightforward, however, I am unable to get an exact answer to the problem. I have narrowed it down to four possibilities one from $\{18, 43, 68, 93\}$.
The approach
We ...
- 136
0
votes
1
answer
34
views
Verification of quotient ring by Chinese remainder theorem
If F is a field then is $F[x]/\left<x^2\right> = F \times F$ correct by CRT ? Can we write $F[x]/\left<x^2-1\right> = F \times F$ by CRT ? I think both can be written in the ...
- 89
1
vote
2
answers
308
views
1000000 consecutive numbers divisible by the square of a prime [duplicate]
I am trying to prove there exist 1000000 consecutive numbers divisible by the square of a prime.
I have already tried several ways
prove that the alternative is impossible didn’t work because it’s ...
- 181
0
votes
0
answers
121
views
Quadratic residue and Chinese Remainder Theorem [duplicate]
I have been casually reading a set of notes (page 30 in reader) on number theory, but I am not certain on one of the steps in the reasoning. Here is a quote:
What can we say about $w^2 ≡ −3\mod 4n$? ...
- 2,165
0
votes
1
answer
66
views
Example 1.2 Opera de Cribro
I'm reading the book "Opera de Cribro" by J. Friedlander and H. Iwaniec, and Example 1.2 states
Edit: Here $$A(x)=\sum_{m~:~m^{2}+1\leq x}1~~,~~A_{d}(x)=\sum_{\substack{m~:~m^{2}+1\leq x}\\...
- 879
3
votes
1
answer
127
views
Chinese Remainder Theorem and reduced system of residues
I need help understanding the following statement:
If $\gcd(a,q)=1$ then by the Chinese Remainder Theorem, $\frac{a}{q}$ has a unique representation modulo 1 of the form $$\sum_{p}\frac{a(p^u)}{p^u}$$...
- 87
0
votes
0
answers
76
views
Chinese Remainder Theorem in Structure Theorem for f.g. Modules over a PID
I have been asked by my Algebra professor, to explicitly determine the Chinese Remainder Theorem in the proof of the Structure Theorem for f.g. Modules over a PID.
Here's what I know:
$\textbf{...
- 153
0
votes
1
answer
52
views
Missing a detail about Chinese Remainder Theorem and $Z$ Ring isomorphisms.
I'm trying to prove that $\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/mn\mathbb{Z}$ holds only when $\gcd(m,n)=1$ or in simpler terms when $n,m$ are coprime integers. So far I ...
- 736
0
votes
0
answers
97
views
Remainder of a square
Let R represent the function that, given two inputs, a and b, returns the remainder of a when divided by b. E.g.:
if $$a = bx + c$$, then $$R(a, x) = c$$
This remainder function has a lot of ...
- 1
0
votes
0
answers
30
views
Reverse a mod in an equation
Being quick and to the point, I have the following equation.
(A * M)%F = B
I want to solve for M. How do you move the modular F?
- 11
2
votes
1
answer
96
views
Find solution using infinite descent.
Can someone help with a task? Need to find a solution other than $(0,0,0) $ with infinite descent. $x,y,z\in\mathbb{Z}$. Any help would be appreciated.
The equation is $x^2-3y^2=2z^2$.
I tried to ...
- 33
1
vote
1
answer
105
views
Does this system of congruences have a solution? [duplicate]
I have the following congruence equation system:
$$ \left\{ \begin{array}{c} x \equiv 7 \pmod{7} \\ x \equiv 4 \pmod{12} \\ x \equiv 16 \pmod{21} \\\end{array} \right. $$
I understand that:
$$x\equiv ...
- 37
4
votes
1
answer
321
views
Prove that there exist primes $p_{i}$ such that $\prod_{i=1}^{k}p_{i} \mid \sum_{i=1}^{k}(p_{i})^{a_{i}}$
If $k\geq 3$ is a given positive integer, prove that there exist prime numbers $p_{1}<p_{2}<\cdots<p_{k}$ and positive integers $a_{1},a_{2},\cdots,a_{k}$, such that
$$p_{1}p_{2}\cdots p_{k} ...
- 92.6k
0
votes
2
answers
246
views
Chinese Remainder Theorem, discrete math problem [closed]
$5^{2003}$ $\equiv$ $ 3 \pmod 7 $
$5^{2003}$ $\equiv$ $ 4\pmod{11}$
$5^{2003} \equiv 8 \pmod{13}$
Solve for $5^{2003}$ $\pmod{1001}$ (Using Chinese remainder theorem).
0
votes
0
answers
36
views
Chinese remainder theorem when modulus are not distinct, is my solution right? also - is this a good way to solve such kind of questions? [duplicate]
i learnt about the Chinese remainder theorem, and im trying to solve the following question:
find the minimal solution x for
(1)x = 11 mod 24
(2)x = 5 mod 18
(3)x = 5 mod 30
i know that in order to ...
- 1
5
votes
1
answer
263
views
Can you generalise the Chinese Remainder Theorem to noncommutative rings without identity?
Ultimately, my question is: does the following theorem hold?
Let $I_1, ..., I_n$ be ideals of some ring $R$, with $R = I_i + I_j$ for $1 \leq i < j \leq n$.
Then for any $r_1, ..., r_n \in R$ ...
- 155