Questions tagged [chinese-remainder-theorem]

For questions related to the Chinese Remainder Theorem and its applications.

Filter by
Sorted by
Tagged with
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 "...
Arthur Queiroz Moura's user avatar
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 \...
calculatormathematical's user avatar
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)$...
Angelo Mark's user avatar
  • 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 ...
Sruthi's user avatar
  • 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 ...
CREATIVITY Unleashed's user avatar
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 ...
affkoff's user avatar
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 ...
Mixoftwo's user avatar
-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(...
Bruh's user avatar
  • 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 ...
user9855939's user avatar
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 ...
hack03er's user avatar
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 \...
Crango's user avatar
  • 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 $...
Oopsilon's user avatar
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 $\ \...
Adam Rubinson's user avatar
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 ...
stoic-santiago's user avatar
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}...
mLstudent33's user avatar
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 ...
PPgull's user avatar
  • 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\...
Dick Grayson's user avatar
  • 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 ...
Josh's user avatar
  • 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 ...
Sann's user avatar
  • 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 ...
Suraj Kulkarni's user avatar
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 :$$...
tonythestark's user avatar
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:...
Ecir Hana's user avatar
  • 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?...
Rafaelo's user avatar
  • 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 ...
badatalg's user avatar
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})...
Edix's user avatar
  • 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 ...
Lamda Electronics's user avatar
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 ...
Anon's user avatar
  • 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?
Anonymous98737943's user avatar
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}$ ...
Ibrahim Hasaan's user avatar
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} \...
Juan Moreno's user avatar
  • 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 ...
Don Freecs's user avatar
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? ...
Ridertvis's user avatar
  • 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 ...
baron jary's user avatar
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 ...
vengy's user avatar
  • 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 ...
Manu Anish's user avatar
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 ...
Pritam Roy's user avatar
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 ...
VickyG's user avatar
  • 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$? ...
legionwhale's user avatar
  • 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}\\...
Nah's user avatar
  • 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}$$...
cho221's user avatar
  • 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{...
user9888663's user avatar
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 ...
Alp 's user avatar
  • 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 ...
João Sá's user avatar
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?
kmart875's user avatar
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 ...
Katli's user avatar
  • 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 ...
Boorger's user avatar
  • 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} ...
math110's user avatar
  • 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).
Timothy Jason 's user avatar
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 ...
Guy's user avatar
  • 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$ ...
Sasha's user avatar
  • 155

1
2 3 4 5
18