Questions tagged [chinese-remainder-theorem]
For questions related to the Chinese Remainder Theorem and its applications.
820
questions
0
votes
0
answers
25
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
0
answers
21
views
Recursive Modular Arithmetic Problem with Pirates and Coins
Four pirates discover a chest of gold coins. The first pirate divides the gold coins in the chest into 4 piles of coins, each having the same number of coins, and finds that there is 1 coin left over ...
- 19
0
votes
0
answers
28
views
show that there are arbitrarily long sequences of consecutive positive integers which are not sums of two squares
Let $p_1, p_2, . . . , p_k$ be different prime numbers. By the Chinese Remainder theorem, show that for each $k ∈ N$ there exists an integer n such that $p_1 |n+1; p_2 |n+2; ...; p_k |n+k$ but $p^2_k$ ...
- 39
1
vote
1
answer
76
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 ...
- 23
1
vote
1
answer
56
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
280
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} ...
- 1
0
votes
2
answers
67
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
35
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
3
votes
1
answer
108
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$ ...
- 135
1
vote
0
answers
23
views
Ring isomorphism between $(k[x,y]/(xy))/(x+y-a)$ and $k\times k$
Let $k$ be a field and let $a\in k$ be a non zero element. Consider the quotient ring $A = k[x,y]/(xy)$. If $f\in k[x,y]$ we denote by $\overline{f}$ its image in $A$. Now consider the quotient ring $...
- 1,865
0
votes
1
answer
132
views
Prove a number is pseudoprime with Sophie Germain
Let p be a Sophie Germain prime. Let q = 2p + 1. Let a = −q − 2p. Given that q ≡ 3
(mod p − 1), prove that pq is a pseudoprime to base a.
I want to show pq is pseudoprime to base a but I am struggling ...
- 57
0
votes
0
answers
27
views
Isomorphism between Rings using Chinese Remainder Theorem
Let $A_n(K)$ be the vector space of applications betwen $\mathbb{Z}_n$ and the field $K$, consider it as a ring with the convolution product $(f*g)(t) = \sum_{m \in \mathbb{Z}_n} f(t)g(t-m)$.
If $K$ ...
- 232
0
votes
0
answers
37
views
Proof that the direct sum of two cyclic modules is cyclic
I've seen the proof that for gcd$(m,n)=1$ the product $\mathbb{Z}/{n \mathbb{Z}} \times \mathbb{Z}/{m \mathbb{Z}}$ is cyclic since it is isomorphic to $\mathbb{Z}/{nm \mathbb{Z}}$ by the Chinese ...
- 143
-2
votes
1
answer
56
views
Chinese remainder theorem without co-prime modulus, and unknown difference
How can I generalize the solution if the modulus is not co-prime. I am familiar with the following.
$\newcommand{\lcm}{\mathrm{lcm}}$Suppose you have a system of two congruences
$$\tag{two}
\begin{...
1
vote
0
answers
28
views
Strong approximation for maximal orders in central division algebras
The Chinese remainder theorem holds for Dedekind domains, and implies that if $\mathfrak{p}_1,...,\mathfrak{p}_n$ are prime ideals of a Dedekind domain $R$, and $\{a_1,...,a_n\}\subset frac(R)$, $\{...
- 251
0
votes
0
answers
130
views
The formula that counts the number of averages of $2k$-separated prime pairs in the interval $[n + 2k, (n+1)^2 - 2k]$ has the following form.
Let $k \geq 1$ and $n \geq k+1$. Then the formula:
$$
f(k,n) := \sum_{d \mid n\#} (-1)^{\omega(d)}\sum_{c \mid d \\ \gcd(c, 2k) = 1} \left(\lfloor \dfrac{(n + 1)^2 - 2k - x_{c,d}}{d} \rfloor + \...
- 19.5k
1
vote
0
answers
21
views
Modular arithmetic with variable exponent and base.
The question was:
*Find all $n \in \mathbb{N}$ for which $2^{2^n}-2^{n^2}$ is divisible by 7.
I think I found the correct solution but I was unable to find the correct answer and since the numbers are ...
- 425
0
votes
1
answer
57
views
Is it possible to calculate where the first point in “a_n = a_(n-1) + 2 with starting point C” equals a square (series with the same growth)?
Background:
Solving this could lead to something revolutionary which is why I don't think it is possible ... but it seems feasible. Despite the seemingly simplistic question, it is actually quite ...
- 1
2
votes
1
answer
58
views
I don't understand a part of the solution involving Chinese remainder theorem
This is the problem statement:
Prove there are infinitely many natural numbers $x = \overline{a_{k}a_{k-1}...a_{2}a_{1}}$, (where $a_{k} \neq 0$) such that $x$ and $x^2$ have the same k-digit ending.
...
- 109
0
votes
0
answers
55
views
Can the Chinese Remainder Theorem be proved for a commutative ring without unity? Or if $I+J \neq R$?
I apologize for this not being a more specific question. I am just wondering what conditions are "necessary" for the Chinese Remainder Theorem to hold true. I know that we need a surjective ...
- 239
0
votes
0
answers
61
views
Find element of order X using Chinese Reminder Theorem
For a school project I'm implementing these Paillier performance improvements.
In chapter 2.2 Scheme 3 subsection Key Generation and Secure Choice of Parameters there are remarks on how to efficiently ...
- 1
1
vote
3
answers
198
views
Using the Chinese Remainder Theorem, $17x \equiv 9 \pmod{276}$
I want to uses the Chinese Remainder Theorem to solve $17x \equiv 9 \pmod{276}$ by breaking it up into a system of three linear congruences,
$$17x \equiv 9 \pmod{3}$$
$$17x \equiv 9 \pmod{4}$$
$$17x \...
- 101
1
vote
0
answers
79
views
Find an integer $x$ such that $x \equiv 3$ (mod $4$) and $x \equiv 5$ (mod $9$)
For this question I basically used the Chinese Remainder Theorem from my book. I just want to make sure my reasoning and logic was correct:
Notice that $4$ and $9$ are relatively prime so the ...
- 1,305
2
votes
1
answer
147
views
Quotient ring $\frac{\mathbb{Z}_n[x]}{⟨f(x)^2⟩}$
I know from Chinese remainder theorem that:
If $\mathbb{F}$ is a field and suppose that $ f(x)\in\mathbb{F}[x]$ is factored into distinct irreducible factors $f(x)=f_1(x).f_2(x)...f_m(x)$,then we ...
- 694
1
vote
1
answer
54
views
Chinese Remainder Theorem for integral ring homomorphisms
Let $A\to B$ be an integral homomorphism of commutative rings, $\mathfrak p\subseteq A$ be a prime ideal and $\mathscr Q$ be a finite set of prime ideals of $B$ lying above $\mathfrak p$.
I ask if the ...
- 15.3k
2
votes
1
answer
67
views
Incongruent Solutions of a Quadratic congruence
I have been reading up on finding incongruent solutions of quadratic congruences and have stumbled upon an answer to a question asked here. The answer I am confused about is the following:
"if ...
- 51
0
votes
0
answers
53
views
A problem of consecutive square full integers.
I am stuck with the following problem of number theory.A number $n$ is said to be square full if $p^2|n$ for some prime $p$.
Let $P(k)$ be the product of all primes $\leq k$.Then show that there ...
- 2,005
0
votes
0
answers
21
views
From a set of markers placed in rows with some remainders, find the smallest smallest number of markers that the set could contain.
If a set of markers is placed in rows of $4$ each, there are $2$ markers left over; if in rows of $5$ each, there are $3$ left over; and if in rows of $7$ there are $5$ left over. What is the smallest ...
- 117
0
votes
0
answers
16
views
Formula for solving a product of factors modulus given congruence relations for the factors
Given a large number $x$ and a set of congruence relations:
$$
for\ n \in N: x \equiv a_n (mod\ b_n)
$$
How can I solve for $a_\pi$ in the following equation:
$$
x = a_\pi(mod\prod_{n\in N}b_n)
$$
...
- 113
2
votes
0
answers
89
views
Chinese Remainder Theorem for Hurwitz quaternions
I know that if we have a noncommutative ring the CRT (Chinese Remainder Theorem) doesn't work and I know that the CRT works for all PIDs (Principal Ideal Domains).
My question is:
In the case of the ...
- 187
0
votes
1
answer
73
views
If $R$ is a ring, what does $R^2$ mean in the Chinese Remainder Theorem? [duplicate]
In ring theory, the Chinese Remainder Theorem is stated as follows.
Let $A_1, \dotsc, A_n$ be ideals in a ring $R$ such that $R^2 + A_i = R$ for all $i$ and $A_i + A_j = R$ for all $i \neq j$. If $b_1,...
- 2,997
-2
votes
2
answers
58
views
Chinese Remainder Theorem when n values are not coprime? [duplicate]
$$ x\equiv 2 \mod 20 $$
$$ x\equiv 7 \mod 15 $$
setting $a \equiv b \mod n$
how would you approach this as the two $n$ values are not coprime?
I've broken down the $ 7\bmod15 $ into $x\equiv 7\mod3$ ...
- 1
2
votes
0
answers
106
views
Euler Fermat theorem and chinese remainder theorem problem
For a positive integer $n$, let $n = p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m},$ where the $p_i$ are distinct primes and each $k_i$ is a positive integer, and define $\gamma(n) := \operatorname{lcm}(\phi(p_1)...
- 766
2
votes
2
answers
237
views
Solve: $x^2\equiv 1 \pmod{20},x^2\equiv 6 \pmod{15},x^2\equiv 9 \pmod{18}.$
I want to solve: $x^2\equiv 1 \pmod{20}, x^2\equiv 6 \pmod {15}, x^2\equiv 9\pmod{18}.$ This is a system of congruence equations, but these are not linear and moduli are not coprime. So,we cannot ...
- 2,005
-2
votes
1
answer
50
views
Chinese Remainder Theorem (uniqueness proof)
I would like to get an explanation of how to proof the uniqueness of the solution of s system of congruences. I have already read 4 books about it but none of them does not explain me an specific part ...
- 437
1
vote
3
answers
103
views
Prove that $x^2+3=0 \text{ can be solved in } \mathbb{Z}/7^k\mathbb{Z} \quad \forall k$.
Prove, that $x^2+3=0 \text{ can be solved in } \mathbb{Z}/7^k\mathbb{Z} \quad \forall k$. It's a practice problem in my abstract algebra class, that many people solved but I didn't. The topic of the ...
user973248
0
votes
3
answers
178
views
Small lemma on moving up multiplicative inverses of powers needs explanation
I am reading about a lemma that shows how to lift up a multiplicative inverse. I.e. if we know that $3\cdot 3 \equiv 1 \pmod {2^3}$ then we know that $3\cdot 43 \equiv \pmod {2^6}$
To go from $\pmod {...
- 1,517
-1
votes
1
answer
58
views
Are these incremements a valid/useful pattern when mapping between modulo (crt)
I have been reading about the CRT and noticed the following pattern.
Let's say that we are mapping the number $N \pmod {21}$ to the corresponding congruences $\pmod 7$ and $\pmod 3$.
For convenience I ...
- 1,517
3
votes
3
answers
61
views
How to find a number $n$ when $n$ mod $n_1$ and $n$ mod $n_2$ is given? [closed]
For example:
suppose we need to find x given that x mod 7 = 5 and x mod 13 = 8.
x = 47 is a solution but needs hit and trial.
Is there any shortcut to calculate such number?
0
votes
0
answers
43
views
How does this Residue Number System table work?
Suppose we have an array of coprime values. For example, $7,13,17$ that we wish to use as a base to represent numbers using the Residue Number System. It looks like this microsoft code does something ...
- 543
2
votes
3
answers
105
views
Find a solution to congruence system $x\equiv 3\pmod{7}$ and $x\equiv 9\pmod{13}$
I'm stuck with following problem and would need some help:
Express the following congruence system as a single congruence equation
$$
x\equiv 3\pmod{7}\\x\equiv 9\pmod{13}
$$
i.e.
$$
x\equiv a\pmod{b}...
- 23
2
votes
2
answers
60
views
Chinese Remainder Theorem - unclear step in algorithm
I have a question regarding the CRT. There's one step in the algorithm that I don't understand, and I couldn't find the explanation anywhere.
I'll give an example question and point out which part ...
- 23
0
votes
0
answers
75
views
Prove that there exists an integer $a$ such that $n|a^2-a$. [duplicate]
Let $n>1$ be an integer, and let $k$ be the number of distinct prime divisors of n. Prove that there exists an integer $a$, $(1)1<a<\frac{n}{k}+1$, such that $(2)$ $n|a^2-a$.
We can rewrite $...
- 531
0
votes
0
answers
47
views
Finding all vectors $(x_1, x_2, x_3) \in \mathbb{Z}_{2021^2}^3$ such $x_1x_2x_3 \equiv 43 \;(\text{mod } 2021^2)$
I am trying to find all vectors $(x_1, x_2, x_3) \in \mathbb{Z}_{2021^2}^3$ that satisfies following condition
$$x_1x_2x_3 \equiv 43 \;(\text{mod } 2021^2)$$
Since $2021^2 = 43^2 * 47^2$ and $43, 47$ ...
- 691
2
votes
1
answer
175
views
What is the property of co-primes that allows CRT to work?
I have been reading about the Chinese Remainder Theorem and I have the following question:
Basically the CRT says that there is a $1$ to $1$ correspondance between a number $N \in [0, m\cdot n)$ and ...
- 1,517
7
votes
1
answer
319
views
Tensor product $L \otimes_K L$ has no nilpotent elements iff $I/I^2=0$
Let $L \supset K$ be a finite extension of fields.
The diagonal $L \otimes_K L$ we can endow
with structure of $L$ algebra via
$L \to L \otimes_K L,\ l \mapsto l \otimes 1_L$.
Especially $L \otimes_K ...
- 811
1
vote
0
answers
89
views
Show that there are arbitrarily large intervals of consecutive integers, none of which is free of squares.
**Definition:**A whole number is free of squares if it is not divisible by the square of any whole number greater than $ 1 $.
Consider the next arbitrary interval of consecutive integers $ (m + 1, m +...
- 181
0
votes
1
answer
59
views
Congruence system \begin{cases} 3x \equiv 4 \pmod{7}\\ 5x \equiv 9 \pmod{11} \end{cases} [duplicate]
I've started to study number theory, I completely do not understand from my notes how to work this out. Could anyone show me with simple example how to solve this?
\begin{cases}
3x \equiv 4 \pmod{7}\\
...
- 21
2
votes
0
answers
61
views
Can we use Chinese remainder theorem to "shrink" a field? attempt 2
Can someone point me to someone that can prove the following, or help me find something similar that is provably correct? See the link near the bottom of this question for a perhaps easier ...
- 5,921
0
votes
1
answer
73
views
Can we use Chinese remainder theorem to "shrink" a field?
Suppose that we have a field $p^k$, and we want to express values in this field modulo smaller fields $(q_1)^k$, $(q_2)^k$,... I believe that there is a way to do this using the Chinese remainder ...
- 5,921