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

learn more… | top users | synonyms

1
vote
2answers
32 views

Calculating the discrete logarithm

I'm given a prime number $p = 1217$ I'm also given the following equations: $ 40 = \log2 \mod 64 $ $ 63 = \log3 \mod 64 $ $ 13 = \log5 \mod 64 $ $ 13 = \log2 \mod 19 $ $ 10 = \log3 \mod 19 $ $ ...
1
vote
1answer
38 views

Chinese Remainder Theorem Consequence 2 [duplicate]

The Chinese remainder theorem as stated in my textbook: If $a,b \in \Bbb Z $ such that $\gcd(a,b) = 1$ then for arbitrary $c,d \in \Bbb Z$ there exists an $x \in \Bbb Z $ with $x \equiv c\bmod a$ and ...
1
vote
3answers
51 views

Definitions of the Chinese Remainder Theorem

The Chinese Remainder Theorem can be stated in a few ways: (i) If $N = N_1N_2\cdots N_k$ and the $N_i$ are pairwise coprime we have a canonical isomorphism $$\mathbb{Z}/N\mathbb{Z} \cong ...
3
votes
1answer
73 views

Fix $k∈\Bbb{N}$. An integer $n$ is said to be $k$-th power free if there exists no prime $p$ such that $p^k | n$…

Fix $k∈\Bbb{N}$. An integer $n$ is said to be $k$-th power free if there exists no prime $p$ such that $p^k | n$. Prove that for any $m∈\Bbb{N} $ greater that 1, there exists $m$ consecutive integers ...
1
vote
4answers
77 views

Determine whether $x^2 - 14x + 30 \equiv 0$ mod 1615 is solvable. If so, find its solutions…

Determine whether $x^2 - 14x + 30 \equiv 0\pmod{1615}$ is solvable. If so, find its solutions. I assume the best way to solve this is via Chinese Remainder Theorem, but first i would have to break ...
-1
votes
0answers
24 views

Finding order of solution to a system of congruences

I'm working on this problem: I'm not really sure where to start. I'm pretty sure I should use the Chinese remainder theorem. Can you help me out?
1
vote
1answer
31 views

Consecutive Answers to Chinese Remainder Theorem

We'll start with 2 congruences only. We'll allow only numbers that when divided by 6, don't have a remainder of 3. Also, only numbers that have a remainder of 2 or 4 when divided by 5: $\equiv ...
0
votes
1answer
27 views

Having trouble with understand the following derived equation by Euler Theorem..

We have the following equations $$\begin{align} d_p=&\ d\mod{(p-1)}\tag5 \\ d_q=&\ d\mod{(q-1)}\tag 6 \\ x_p=&\ y^{d_p}\mod p\tag 7 \\ x_q=&\ y^{d_q}\mod q\tag 8 \\ x=&\ ...
0
votes
2answers
47 views

Bézout's Identity of polynomials?

Let $P=X^3−7X+6$, $Q = 2X^2+ 5X − 3$ and $R = X^2 − 9 ∈\mathbb Q[X]$. What are $S$ and $T ∈\mathbb Q[X]$ such that $PS + QT = R$? I have calculate the greatest common divisor of $P,Q,R$ are ...
3
votes
0answers
28 views

Recreational math dealing with twin primes

This is kinda recreational math with a goal in mind of progressing further toward a proof of the twin prime conjecture. Consider this: We start with a random prime: $109$ $3*109=327$ $327 ...
1
vote
0answers
34 views

Chinese Remainder Theorem with form I have not seen

One of my professors gave out a practice exam for a Discrete Mathematics test, and I'm having a little trouble with this problem: "Use the Chinese Remainder's Theorem to find ALL solutions to the ...
0
votes
2answers
72 views

Reverse of Chinese Remainder Theorem

For the following: $(102n-51) \not\equiv 2 \pmod {2,3,5,7,11,13,...,\sqrt{102n-51}}$ (That's probably completely incorrect use of symbols, but I mean not equivalent to 2 mod any prime less than ...
1
vote
1answer
40 views

Chinese remainder theorem, how can I prove it?

I want to show that $\mathbb Z/pq\mathbb Z\cong \mathbb Z/p\mathbb Z\times \mathbb Z/q\mathbb Z$ where $(p,q)=1$. I consider the morphism $$[a]_{pq}\longmapsto ([a]_p,[a]_q).$$ If I have the ...
3
votes
1answer
39 views

Does the method of substitution always work for solving linear congruence systems?

By substitution, I mean if I had this example: $$ x \equiv 1 \pmod{5}$$ $$x \equiv 2 \pmod{6}$$ Then I would solve it by solving this equation... $$ x = 1 + 5k \equiv 2 \pmod{6}$$ $$k \equiv 4 ...
1
vote
0answers
23 views

Let $m =\prod_{i=1}^{r} p_i^{α_i}$, with $α_i \ge 1$ and $p_i \ge 3$ for each $i$, be the canonical representation of $m$ and…

Let $m =\prod_{i=1}^{r} p_i^{α_i},$ with $α_i \ge 1$ and $p_i \ge 3$ for each $i$, be the canonical representation of $m$ and let $a$ be relatively prime to $m$. Show that $x^2 \equiv a \pmod m$ is ...
0
votes
2answers
22 views

Binomial Expansion polynomial with remainder

Got his question: (a) Use the binomial theorem to expand (x+1)^99, and show that (x+1)^99 = x^2f(x) + 99x + 1, where f(x) is a function in x. (b) Using the result in (a), find the remainder when 7^99 ...
0
votes
1answer
13 views

System of congrences

If $m$ is an odd integer and $n \in \mathbb N$, prove that the system of congruence $2x \equiv 2n (mod\, m)$ $x \equiv m(mod \, 2^n) $ has exactly one integer solution $x$ with $0 \le x \lt 2^nm$ ...
1
vote
1answer
13 views

Show that $q'$ is the quotient of euclidean division of the number $n$ by $ab$

Let $n\in N$ and $a,b\in N$: 1- $q$ the quotient of euclidean division of $n$ by $a$ 2- $q'$ the quotient of euclidean division of $q$ by $b$ Show that $q'$ is the quotient of euclidean division ...
1
vote
1answer
83 views

There is a general and his army of 13 soldiers (14 people in total) raided an enemy base…

There is a general and his army of 13 soldiers (14 people in total) raided an enemy base. After conquering the base, they tried to divide the supplies they found into 14 equal portions. However, when ...
0
votes
1answer
32 views

Solve the conditional congruence 371x ≡ 287 (mod 460)…

Solve the congruence: a.) 371x ≡ 287 (mod 460) b.)2837x ≡ 1601 (mod 1710) -Currently covering a section on the Chinese remainder theorem and did several other conditional congruence problems but ...
0
votes
2answers
23 views

Find integer $x$ such that -2310 ≤ $x$ ≤ 2310…

Find integer $x$ such that -2310 ≤ $x$ ≤ 2310, and $x$ ≡ 1 (mod 21), $x$ ≡ 2 (mod 20), $x$ ≡ 3 (mod 11) -Currently covering a section on the Chinese remainder theorem and having trouble figuring ...
0
votes
1answer
22 views

Why does m dividing a − b mean that a and b have the same remainer under division by m?

Why does $m$ dividing $a − b$ mean that $a$ and $b$ have the same remainer under division by $m$? By the definition of a “remainder,” we can write $a = im + r_1$, where $r_1$ is the remainder under ...
1
vote
1answer
38 views

Prove that there exist $n$ consecutive positive integers with the $i$th integer divisible by the $i$th prime

Prove that for any positive integer $n$, there exist $n$ consecutive positive integers $a_1, a_2,...,a_n$ such that $p_i |a_i $ for each $i$, where $p_i$ denotes the $i$th prime? Having a lot of ...
6
votes
1answer
40 views

Modular DNA as a way of classifying numbers

I'm going to start with a few examples. I may need someone to help correct wording. I'm going to write what I call the modular fingerprint of the following numbers. It's the list of the remainders of ...
0
votes
1answer
46 views

Use the Chinese Remainder Theorem to find the smallest element of a set

Use the Chinese Remainder Theorem to find the smallest element of $$\left\{n\in \mathbb{N}: \sqrt{\frac{n}{2}}, \sqrt[3]{\frac{n}{3}}, \sqrt[5]{\frac{n}{5}}\in \mathbb{N}\right\}$$ I have played ...
0
votes
1answer
38 views

Assumption in Proof on the Inverse Mapping of the Chinese Remainder Theorem

Outline: Let $\phi: R_{m_1 m_2 \cdots m_n} \to R_{m_1} \times \cdots \times R_{m_n}, a \mapsto (a \mod m_1, \ldots, a \mod m_n)$ be the mapping of the Chinese Remainder Theorem ($R = Z$ or $R = F[x]$ ...
2
votes
1answer
20 views

CRT - non-linear system of equations

I don't know how to solve system of equations using CRT when there is some quadratic/cubic variable. For example: System 1: $$\boxed{x^3 \equiv 1 \pmod{3}}$$ $$12x \equiv 9 \pmod{15}$$ ...
1
vote
0answers
33 views

chinese remainder theorem for gaussian integers

I want to show that Chinese Remainder Theorem(CRT) has a unique solution over gaussian integers. But when I choose $x=4+5i$ and determine coprime modulo numbers $1+2i$ and $1+4i$, the simultaneous ...
0
votes
4answers
37 views

What to do if the modulus is not coprime in the Chinese remainder theorem?

Chinese remainder theorem dictates that there is a unique solution if the congruence have coprime modulus. However, what if they are not coprime, and you can't simplify further? E.g. If I have to ...
6
votes
1answer
64 views

An Analogue of Chinese Remainder Theorem for Groups

I am trying to prove the following analogue of Chinese remainder theorem for groups: Let $G$ be group and let $H_1, \dots, H_n$ be its normal subgroups such that their indices $[G : H_1], \dots, [G : ...
-3
votes
2answers
38 views

Theorem on the interpretation of the ring $Z_n$ [closed]

$(m, n)=1 \Rightarrow Z_{mn} \cong Z_m$ x $Z_n$ Can anyone please help me with proof for this theorem? Thanks in advance.
0
votes
1answer
47 views

Using Chinese Remainder Theorem to find an integer $x$ for which $ x\equiv 3\pmod 4 x\equiv 5\pmod 9 x\equiv 10\pmod {35} $

Hello I have got problems with understanding the reduction method in CRT. We have got system like this $$x\equiv 3\pmod 4$$ $$x\equiv 5\pmod 9$$ $$x\equiv 10\pmod {35}$$ There is a way to do this ...
0
votes
2answers
25 views

Quadric modular equation

I had to calculate $x$ from $x^2 =x\pmod{10^3}$ I knew that $a = b\pmod{cd} \Rightarrow a=b \pmod c\ \land a=b \pmod d$ when $\gcd(c,d)=1$ Therefore I got two equations : $x^2 = x \pmod 8$ $x^2 ...
1
vote
0answers
26 views

When is the sum of three reduced rationals equal to an integer

When is the sum of three reduced rationals equal to an integer? This may be a duplicate of Question 1550437 but even if it is, there is no answer associated with this other question. Given three ...
0
votes
2answers
81 views

Evaluate all the square roots of 4 mod 77. [closed]

I have an exam coming up an this will be one style of question can anyone please walk me through how it is done? Sorry I am just totally confused and do not how to start Evaluate all the square roots ...
0
votes
0answers
48 views

General Chinese remainder theorem proof

Okay, so we have the Chinese Remainder Theorem: If $m_1$ and $m_2$ are coprime then the simultaneous congruences $\left( x \equiv a_1 \mod m_1 \right)$, $\left( x \equiv a_2 \mod m \right)$ have a ...
0
votes
1answer
22 views

Why '$3t \equiv 2 \pmod 5 \implies t \equiv 4 \pmod 5$' is true in resolving congruence?

I want to resolve this system of equations \begin{equation} \begin{cases} x & \equiv & 1 & \pmod 3\\ x & \equiv & 3 & \pmod 5\\ x & \equiv & 2 & \pmod 7\\ ...
1
vote
2answers
26 views

How can I apply the Chinese Remainder Theorem when a modulus is the square of another one?

For example: $$\begin{cases} x = 23 \mod 3 \\ x = 8 \mod 9 \\ x = 33 \mod 4 \end{cases}$$ I know that when two moduli are not mutually prime (for example: $$\begin{cases} x = n \mod 45 \\ x = m \mod ...
1
vote
0answers
13 views

CRT general equal for three congruences - correct?

I saw someone ask a question regarding the congruences below. $c≡1 \mod 143$ $c≡315 \mod 323$ $c≡167 \mod 667$ I tried to solve them with this equation: For any number of congruences $x≡a\mod n$, ...
0
votes
3answers
23 views

Solve three congruences using CRT

How do I solve the following Congruences= $c ≡ 1 \mod 143$ $c ≡ 315 \mod 323$ $c ≡ 167 \mod 667$ I know that the moduli are coprime so there will be a unique solution. Secondly, I know that the ...
4
votes
0answers
106 views

Description of the equalizer of $\prod _j R/I_j \rightrightarrows \prod _{i,j}R/(I_i+I_j)$

This will hopefully be my last question about the chinese remainder theorem. I have asked several questions in an attmept to get a general version without conditions on the ideals which will trivially ...
9
votes
1answer
158 views

Chinese remainder theorem as sheaf condition?

The chinese remainder theorem in its usual version says that for a finite set of pairwise comaximal ideals $R/\bigcap _jI_j\cong \prod _j R/I_j$. In the binary case, the following general statement ...
-1
votes
1answer
25 views

Chinese Remainder Theorem for infinite system

I have a trouble understanding p.7 of the following article: http://www.edb.gov.hk/attachment/en/curriculum-development/kla/ma/IMO/Nov20155-4online.pdf which says the folllowing: By the same ...
4
votes
2answers
292 views

Prove that $R\cong \mathbb{C}^n$

Let $R=\mathbb{C}[x]/(f(x))$ where $f(x)$ is a polynomial of degree $n>0$ which has $n$ distinct complex roots. Prove that $R\cong \mathbb{C}^n$. I tried to define a homomorphism $\phi$ from ...
4
votes
0answers
53 views

Characteristic and minimal polynomials

Given $A\in\Bbb Z^{n\times n}$, is it possible to find characteristic and minimal polynomials of $A$ by chinese remainder theorem if we know characteristic and minimal polynomials respectively of ...
0
votes
0answers
34 views

Combining solutions of subproblems with CRT when solving discrete logarithm problem with composite modulo

Author of this answer reduces the discrete logarithm problem $a = b^x \pmod{N}$, $N=p q r$, $p,q,r\in {\mathbb P}$ to smaller discrete logarithms problems $a = b^y \pmod{p}$ $a = b^z \pmod{q}$ $a = ...
0
votes
2answers
19 views

$g$ is a primitive root mod $p$ and $h$ is a primitive root mod $q$. Using CRT find $k$ whose order is exactly lcm$(p-1,q-1)$

Let $q$ and $p$ be unique primes. $g$ is a primitive root mod $p$ and $h$ is a primitive root mod $q$. Using CRT find $k$ whose order is exactly lcm$(p-1,q-1)$ I know that $g^{p-1} \equiv 1 ...
1
vote
0answers
30 views

Chinese Remainder theorem clarification needed

I'm trying to solve $p\equiv a\pmod{7}$ and $p\equiv b\pmod{4}$ $m_1=(4)^{-1} \pmod 7$ $m_2=(7)^{-1} \pmod 4$ I need to find $m_1'$ and $m_2'$ which I assumed to be the inverse of $m_1$ and ...
1
vote
1answer
37 views

System of congruences with polynomials

How do I go about solving exercises such as this one: Find all polynomials $f(x)$ in $\mathbb{Z}_3$ that satisfy $$f(x) \equiv 1 \space \space \mathrm{mod} \space \space x^2 + 1$$ $$f(x) \equiv x ...
3
votes
3answers
76 views

Solve $x^2\equiv -3\pmod {13}$

Question 1) Solve $$x^2\equiv -3\pmod {13}$$ I see that $x^2+3=n13$. I don't really know what to do? Any hints? The solution should be $$x\equiv \pm 6 \pmod {13}$$ Question 2) Given $x\equiv \pm 6 ...