Questions tagged [chinese-remainder-theorem]

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

Filter by
Sorted by
Tagged with
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?
user avatar
-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 ...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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} ...
user avatar
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).
user avatar
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 ...
user avatar
  • 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$ ...
user avatar
  • 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 $...
user avatar
  • 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 ...
user avatar
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$ ...
user avatar
  • 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 ...
user avatar
-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{...
user avatar
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)$, $\{...
user avatar
  • 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 + \...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 \...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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) $$ ...
user avatar
  • 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 ...
user avatar
  • 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,...
user avatar
  • 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$ ...
user avatar
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)...
user avatar
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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
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 {...
user avatar
  • 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 ...
user avatar
  • 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?
user avatar
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 ...
user avatar
  • 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}...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
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$ ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 +...
user avatar
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}\\ ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 5,921

1
2 3 4 5
17