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

learn more… | top users | synonyms

1
vote
1answer
28 views

Remainder modulo matrices.

Is it possible to have a consistent definition of $A\bmod_{left} B$ that respects matrix multiplication from left where $A$ and $B$ are two square matrices with non-negative entries? Is there a ...
4
votes
3answers
67 views

Find the last digit of $3^{1999}$

I don't know where I got wrong. My answer is 3, but the answer sheet says 7. Here is what I did: $3^{1999}=(3^9)^{222}*3$. Use Fermat's Little Theorem, $3^9=1$ (mod 10), which results in $3^{1999}=(3^...
1
vote
0answers
49 views

Converse to Chinese remainder, domain, isomorphism as rings

The converse to CRT asks: does $R/(I \cap J)\simeq R/I \times R/J$ imply $I+J=R$? For me $\simeq$ is an abstract ring isomorphism, sending $1$ to $1$, not necessarily $R$ linear, i.e., one of $R$--...
0
votes
1answer
43 views

Help with finding the remainder of $2^{2^n}$ when divided by 13

I have this problem from an algebra course: Find the remainder of $2^{2^n}$ when divided by 13, $\forall n \in \Bbb N$ It's in a section of Fermat's little theorem and Chinese Remainder Theorem ...
2
votes
1answer
15 views

Let $a \in \Bbb Z$ such that $gcd(9a^{25}+10:280)=35$. Find the remainder of $a$ when divided by 70.

I'm stuck with this problem from my algebra class. We've recently been introduced to Fermat's little theorem and the Chinese Remainder Theorem. Let $a \in \Bbb Z$ such that $gcd(9a^{25}+10:280)=35$...
0
votes
1answer
49 views

Solving Chinese Remainder Theorem Algebraically

I am doing a practice problem for my final which asks: Solve the following Chinese Remainder Theorem: $$ x \equiv 2 \pmod{3}, \\ x \equiv 3 \pmod{5}, \\ x \equiv 5 \pmod{7}, \\ x \equiv 7 \pmod{11} \...
1
vote
3answers
43 views

Find the element in $\mathbb{Z}/143\mathbb{Z}$ whose image is $(\overline{10},\overline{11})$ under the Chinese remainder theorem

Find the element in $\mathbb{Z}/143\mathbb{Z}$ whose image is $(\overline{10},\overline{11})$ in $\mathbb{Z}/11\mathbb{Z} \times \mathbb{Z}/13\mathbb{Z}$ under the Chinese remainder theorem So I ...
2
votes
1answer
18 views

Chinese Remainder Theorem When GCD is not 1

I've got this system of equations that I'm trying to solve. I'm pretty sure I have to use the CRT, but to my understanding, it can only be used when GCD of all the mods is 1. I don't want an answer ...
0
votes
0answers
23 views

Solving $n^{th}$ power residue of a congruence

I'm given $x^2$ ≡ -1 mod 365 I know that 365 = $5*73$ so then my congruence becomes, $x^2$ ≡ -1 mod 5 and $x^2$ ≡ -1 mod 73 Since $(-1)^2$ ≡ 1 mod 5 and $(-1)^{36}$ ≡ 1 mod 73 implies that there ...
0
votes
2answers
86 views

Chinese remainder theorem/Fermat's little theorem problem

Prove that $p^4 \equiv 1 \pmod {240}$ for any prime $p>5$. I'm not sure how to go about this at all - I started with some computation to check it works for $\{7,11,13\}$ and they all end in $1$ - ...
0
votes
1answer
27 views

Modulo Arithmetic - Chinese Remainder Theorem

Solve the linear congurence $17x\equiv 3(\mod{2*3*5*7})$ by solving the system: $17x\equiv 3(\mod{2})$ For this one, I simplified to $x\equiv 1(\mod{2})$. Let this $x=5$. $17x\equiv 3(\mod{3})$ ...
0
votes
1answer
15 views

How to permute remainders of CRT between residue classes?

I want to know how can be permuted the remainders of the CRT. How to go from $a \equiv r1 \;(\bmod\; n_1)$ $a \equiv r2 \;(\bmod\; n_2)$ to $b \equiv r1 \;(\bmod\; n_2)$ $b \equiv r2 \;(\bmod\...
1
vote
2answers
41 views

Elementary Number Theory: Chinese Remainder Theorem

Using the facts that $1591=37.43$ and $51=3.17$ compute 1591 mod 51 using the Chinese Remainder Theorem. I started off by letting $x \equiv 1591 \mod 51$ which I then wrote as $x \equiv 1591 \mod 17$...
0
votes
0answers
15 views

Congruences, modular

I need to solve this problem with the Chinese Remainder Theorem: $$ x = b_1N_1x_1+b_2N_2x_2 + ...+b_kN_kx_k $$ N = 17*13*12 = 2652 $$\begin{cases} x≡7 \pmod{17} \\ x≡9 \pmod{13} \\ x≡3 \pmod{12} \...
1
vote
1answer
37 views

How to split congruences so moduli are prime powers?

If I have the linear congruence x=5 mod 84, is this equal to x=2 mod 3, since 3|84? This seems too easy.
0
votes
0answers
23 views

Number of solutions to $f(x)\equiv 0 \mod(11\cdot 19^{2})$

I have been asked to explain why the number of solutions of the polynomial congruence $f(x)\equiv 0 \mod (11\cdot 19^{2})$ cannot be 121, where $f(x)=x^{10}+10x^{8}-17x+12$. Any ideas?
1
vote
2answers
36 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
41 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
54 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 \mathbb{Z}/...
3
votes
1answer
77 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
82 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
vote
1answer
34 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,1,...
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
51 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 $(x+3)$, ...
3
votes
0answers
32 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 \equiv$...
1
vote
0answers
40 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 ...
1
vote
2answers
81 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
42 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
43 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
14 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
15 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
33 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
24 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
23 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
40 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 ...
3
votes
1answer
131 views

A problem on chinese remainder theorem (CSIR NET DEC 2015)

Which of the following intervals contains an integer satisfying following three congruences $$x=2\pmod5\\ x=3\pmod7\\ x=4\pmod{11}$$ $a) [401,600] \\ b)[601, 800] \\ c)[801,1000] \\ d)[1001,1200]$ ...
0
votes
1answer
47 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
40 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
25 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
36 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
38 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
66 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
42 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
48 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
26 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 ...