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

learn more… | top users | synonyms

0
votes
1answer
12 views

Using chinese remainder theorem for solving exponentials with variables

How would you show this for every $n\in N$? $$3^{n^4+n^2+2n+4}\equiv 21\mod 60$$ So as the chines remainder is mentioned, I would start with 60=3*4*5, but then how? Thank you!
0
votes
1answer
37 views

Solvability of $a \equiv x^2 \mod b$

Suppose you want to prove that $\exists x \in \mathbb{Z}$ with $a \equiv x^2 \mod b$. Write $b = \prod_{i = 1}^{k} p_i^{e_i}$, the prime factorisation of $b$. Why is the equivalent with finding ...
1
vote
0answers
61 views

Find the smallest number which leaves remainder 1, 2 and 3 when divided by 11, 51 and 91

While my preparation for exams, came across this question. "Find the smallest number which leaves remainder 1,2 and 3 when divided by 11,51 and 91" Find considerable time in solving this. I have ...
1
vote
1answer
36 views

Solve the system of congruences (CRT)

$$560x \equiv 1 \pmod{3, 11, 13}$$ I found a few (by trial and error) $560x \equiv 1 \pmod{13} \implies x = 1 + 13k$. $560x \equiv 1 \pmod{3} \implies x = 2 + 3k$. $560x \equiv 1 ...
2
votes
0answers
30 views

proof of chinese remainder theorem $x=a_1M_1y_1+…+a_nM_ny_n$?

I can't understand the proof of Chinese Remainder Theorem let $x ≡ a_1 (\text{mod }m_1 ),$ $x ≡ a_2 (\text{mod }m_2 ),$ · · · $x ≡ a_n (\text{mod }m_n )$ such that $m_1,m_2,...,m_n$ are relatively ...
6
votes
0answers
155 views

Converse of Chinese Remainder Theorem

Chinese Remainder Theorem for commutative rings with identity Let $R$ be a commutative ring with identity. If $I, J$ are ideals of $R$ satisfying $I+J=R$, then there is an isomorphism of rings: ...
0
votes
1answer
43 views

Chinese Remainder Theorem example

$$x = 4 \bmod 18$$ $$x = 52 \bmod 96$$ $$x = 6 \bmod 20$$ My current algorithm thinks the answer is $x \equiv 1066 \bmod 1440$ but I don't think there should be a solution to this. The algorithm: ...
1
vote
1answer
43 views

Congruence using extended GCD

$$\eqalign{ x &\equiv 5 \mod 15\cr x &\equiv 8 \mod 21\cr}$$ The extended Euclidean algorithm gives $x≡50 \bmod 105$. I understand now that if we combine the two it implies ...
1
vote
2answers
49 views

Why is this congruence true?

$$\eqalign{ x &\equiv 5 \mod 15\cr x &\equiv 8 \mod 21\cr}$$ The extended Euclidean algorithm gives $x≡50 \bmod 105$. How/why? I am trying to understand how this is true when ...
1
vote
0answers
19 views

Need my CRT work spot-checked

So I have a bunch of equations that look like this: $$k + tx \equiv a \bmod m$$ Where $t$ is the common variable I am solving for among the equations (each equation may have different values for ...
0
votes
1answer
30 views

Why does this imply a congruence does not exist?

Consider $$kx \equiv a \bmod M$$ Where $x,a,M$ are known, solving for $k$. Let $g = \gcd(M,x)$. Why is it the case that if $g$ does not divide $a$, there is no solution?
0
votes
3answers
52 views

Chinese remainder theorem for three equations?

Is there a straightforward approach for solving the Chinese Remainder Theorem with three congruences? $$x \equiv a \bmod A$$ $$x \equiv b \bmod B$$ $$x \equiv c \bmod C$$ Assuming all values are ...
0
votes
1answer
29 views

Application of the Chinese Remainder Theorem for polynomials

Given the polynomials $g(t) = t$ and $h(t) = (t-3)^2 \in \mathbb{C}[t]$, I want to find the smallest (in terms of degree) polynomial $f(t) \in \mathbb{C}$ satisfying $f \equiv 0$ mod $g$ and $f \equiv ...
0
votes
0answers
30 views

A Curious Chinese Remaindering Question

Given integers $A,B,N$ with $0<N<A,B<N(4\log N)^{1+\delta}$ with $\delta>0$ arbitrarily small, do there exist integers $X,Y$ such that $$0<X<A,B<X\log ...
2
votes
3answers
62 views

Problem in proof of Chinese remainder theorem, and applying it.

Please don't mark it as duplicate. First read the whole question. So Chinese Remainder Theorem states that,: Let $n_1,n_2,...,n_k$ be $k$ positive integers which are pairwise relatively prime. If ...
1
vote
2answers
47 views

Is this another way of stating the Chinese Remainder Theorem?

Assume that $I + J = R$. Let $a,b \in R$. Find an element $u$ of $R$ satisfying $a + I = u + I$ and $b + J = u + J.$ I want to work on this, but I feel there's some issue of a missing theorem I ...
1
vote
4answers
34 views

system of modular equations.

$x\equiv 2\pmod3$ $x\equiv 3\pmod 5$ $x\equiv 7 \pmod{11}$ How can I solve this system for $x$? I've tried all kinds of things using divisibility but no success. Any hints of solutions are greatly ...
2
votes
1answer
50 views

Modulo calculation with multiple exponents, via CRT

I'm aware that there are already a few questions like this but unfortunately I wasn't able to find an answer yet. $$ (14^{2014)^{2014}} \pmod {60} $$ So I started off by putting the modular in : $$ ...
1
vote
2answers
65 views

solve $x^2 \equiv 24 \pmod {60}$

I need to solve $x^2 \equiv 24 \pmod {60}$ My first question which confuses me a lot - isn't a (24 here) has to be coprime to n (60)??? most of the theorems requests that. what i tried - $ 60 ...
0
votes
1answer
13 views

The high occurence of a number equals to the last few digits of its own square

Prove (or disprove): For positive integer $n$, define $M_n$ as an $n$-digit positive integer such that in decimal representation, the last $n$ (rightmost) digits of $M_n^2$ is $M_n$ itself. Denote ...
1
vote
2answers
27 views

Find minimal $x\in\Bbb N$ that solves the linear congruence

I need to find minimal $x\in\Bbb N$ that solves the linear congruences: $6x \equiv 2 \pmod {\!4}$ $3x \equiv 6 \pmod {\!9}$ $x \equiv 15 \pmod {\! 17}$ I divided the first congruence by $2$ and ...
5
votes
1answer
56 views

Chinese reminder Theorem and primitive roots

The problem I am working on is "Let $p$ be a prime such that $p\equiv 1\pmod{105}$. Show that there exist integers $n, x, y, z$ such that $p$ does not divide $n$ and $n \equiv 3x^3 \equiv 5y^5 \equiv ...
1
vote
2answers
46 views

Prove: if $a$ is a square mod $p,q$, then it is a square mod $pq$

For distinct odd primes $p,q$, if $x^2\equiv a \pmod {\! p}$ is solvable and $x^2\equiv a \pmod {\!q}$ is solvable, then $x^2\equiv a \pmod {\! pq}$ is solvable. Here, I am also assuming neither $p$ ...
4
votes
3answers
68 views

On the distribution of multiples of 7 into intervals of length 11

Say we have two primes, say 7 and 11. We are to consider the positions of the multiples of 7 inside the (7 buckets of) multiples of $11$. So the buckets of 11 are: $[1,11],[12,22],\ldots ,[67,77]$, ...
1
vote
2answers
84 views

Generalization of Chinese Remainder Theorem

Q: With ring $R$, if $I, J \subseteq R$ are ideals such that $I+J=R$, then the map $R/(I \cap J) \to R/I \times R/J$ given by $a + (I \cap J) \mapsto (a+I, a+J)$ is an isomorphism, broadly ...
3
votes
3answers
75 views

Calculate possible values of $a^4$ mod $120$.

Calculate possible values of $a^4$ mod $120$. I don't know how to solve this, what I did so far: $120=2^3\cdot3\cdot5$ $a^4 \equiv 0,1 \pmod {\!8}$ $a^4 \equiv 0,1 \pmod {\!3}$ $a^4 \equiv 0,1 ...
2
votes
1answer
51 views

Some ring isomorphic to $\mathbb Z[i] / \langle 5 \rangle$

I am trying to find some ring isomorphic to $\mathbb Z[i] / \langle 5 \rangle$ . I know that $\langle 5 \rangle=\langle (2+i)(2-i)\rangle=\langle 2+i\rangle \langle2-i\rangle$ , now if $d$ is the ...
4
votes
6answers
169 views

(14^2014)^2014 mod 60 without a calculator

Calculate without a calculator: $\left (14^{2014} \right )^{2014} \mod 60$ I was trying to solve this with Euler's Theorem, but it turned out that the gcd of a and m wasn't 1. This was my ...
0
votes
1answer
46 views

How do I use the Chinese remainder theorem to find all the square roots of 11 in $\mathbb Z_{35}$?

I understand what the Chinese remainder theorem is. However I am not sure how to apply it to my question. Can someone explain please?
3
votes
1answer
255 views

Euler's theorem: [3]^2014^2014 mod 98

Calculate without a calculator: $$\left [ 3 \right ]^{2014^{2014}}\mod 98$$ I know I have to use Euler's Theorem. As a hint it says I might need to use the Chinese Remainder theorem too. I know ...
0
votes
0answers
11 views

Isomorphism inbetween a factor ring and Cartesian product of factor rings [duplicate]

Let R be principal ideal ring and $a_1, ..., a_n \in R$, with $gcf(a_i, a_j) = 1$, for all $i, j \in \{1, ..., n\}$ (with $gcf$ being the greatest common factor of $a_i, a_j$). Show that the ...
0
votes
1answer
24 views

Why is it important to recognize CRT establishes an isomorphism between $Z/p\#Z$ and $Z/qZ$

As I understand it, it is well known that CRT can be used to show that $Z/p\#Z$ as a ring is isomorphic to the product of the finite fields $Z/qZ$ where $q$ ranges over the primes up to $p$. For ...
1
vote
1answer
77 views

Trouble forming general solution for linear congruence

I was given $$ 6x+14y=4 \space \mod 5 $$ I took this approach: $$ 6x+14y-5z=4, \space \text{ for some } z $$ Let $$ w=\frac{6}{(6,14)}x+\frac{14}{(6,14)}y $$ Then, $$ (6,14)w+5z=4 \quad , \quad ...
0
votes
2answers
39 views

find all the solutions: chinese remainder + fermat theorem

I have following congruences, in first congruence I know I have to use the Fermat theorem for finding the solution but I couldn't understand how, because most of the samples in internet using some ...
0
votes
4answers
53 views

$777^{401} \pmod {1000}$ is?

here's an arithmetic question : find the last $3$ digits of $777^{401}$. I don't know where to start. The chinese remainder theorem gives a double congruence modulo $8$ and $125$ but I don't think ...
2
votes
0answers
37 views

Question about the Chinese Remainder Theorem and the residue class ring ${\bf Z}/p\# {\bf Z}$

In a question that I asked on MO, Terence Tao observed that: The Chinese Remainder Theorem tells us that the residue class ring ${\bf Z}/p\# {\bf Z}$ is isomorphic (as a ring) to the product of ...
0
votes
1answer
128 views

Chinese Remainder Theorem - solving a modulo with big numbers

I have the calculation: $2^{31}\pmod {2925}$ It's for university and we should solve it like: make prime partition $2^{31}$ mod all prime partitions Solve with Chinese Remainder Theorem. I ...
7
votes
0answers
66 views

The difference between the ring version and module version of Chinese Remainder Thereom.

Chinese Remainder Theorem for Commutative Rings If $R$ is a commutative ring with $1$ and $I, J$ are ideals of $R$ that are pairwise coprime or comaximal (meaning $I + J = R$), then $IJ = I \cap J$, ...
5
votes
1answer
101 views

If $R/I \times R/J$ is isomorphic to $R/(I\cap J)$ as $ R $-modules, then $I + J = R$. [duplicate]

If $R$ is a commutative ring with identity and $I$ and $J$ are ideals of $R$ such that $R/I \times R/J$ is isomorphic to $R/(I\cap J)$ as $R$-modules, then $I + J = R$. I know this is the ...
2
votes
1answer
43 views

Show that if $R$ is commutative, then $\mathrm{Ann}(n_1) + \mathrm{Ann}(n_2) = R$.

Let $R$ be a commutative ring with $1$, and let $M$ be a cyclic $R$-module with generator $m$ (so that $M=Rm$). Suppose that $M = N_1 \bigoplus N_2$ for some submodules $N_1$ and $N_2$ of $M$. Let ...
1
vote
1answer
62 views

Chinese remainder theorem to solve $3 \bmod 11$ and $11 \bmod 13$

I'm trying to Decrypt a cipher text which has been encrypted using RSA and whose resulting value is $20$. Public parameters are $N = 143$ and $e = 17$. I've gotten down to equations $$x\equiv3 ...
1
vote
2answers
103 views

Show that $R/(I \cap J) \cong (R/I) \times (R/J) $

My question actually follows from this one: Show that if $I + J = R$, then $R/(I \cap J) \cong R/I \times R/J$ What I don't understand is why is it necessary for $I+J=R$, in order for $$ ...
1
vote
1answer
46 views

There exist arbitrarily long sequences of consecutive integers that are not square-free

Let $a$ and $n$ be positive integers. A sequence of $n$ consecutive integers $(a, a+1, a+2,...,a+(n-1))$ is called a Wolczuk of length $n$ if every integer in the sequence is divisible by some perfect ...
4
votes
2answers
79 views

To Find $a$ such that $2^{1990} \equiv a\pmod {1990}$. [duplicate]

To Find $a$ such that $2^{1990} \equiv a\pmod {1990}$. $1990 = 2 \times 5 \times 199$. Now $a \equiv 0 \pmod {2}$, $a \equiv 4 \pmod{5}$ and $a \equiv 29 \pmod{199}$. Taking first two together we ...
5
votes
2answers
57 views

Simultaneusly solving $2x \equiv 11 \pmod{15}$ and $3x \equiv 6 \pmod 8$

Find the smallest positive integer $x$ that solves the following simultaneously. Note: I haven't been taught the Chinese Remainder Theorem, and have had trouble trying to apply it. $$ \begin{cases} ...
2
votes
0answers
37 views

Why do we keep the LCM modulo in the Chinese Remainder Theorem?

I'm doing my homework and I'm struggling to get an answer. I'm taking number theory and we're working on a problem to solve congruences. We've got: $ x\equiv 1 \pmod{5}\\ x\equiv 3 \pmod{8}\\ x\equiv ...
1
vote
0answers
28 views

Chinese remainder - Error in my solution

I have the following congruence system: $x \equiv 1 \mod 5 \\ x \equiv 2 \mod 7 \\ x \equiv 0 \mod 8 \\ x \equiv 3 \mod 11$ I used the Chinese Remainder Theorem to get a solution, but it only ...
2
votes
3answers
40 views

Chinese Remainder Theorem for $x\equiv 0 \pmod{y}$

Can anyone solve the following system of congruences using CRT step-wise, without skipping any part? $$\begin{cases} x\equiv 3 \pmod{7}\\ x\equiv 3 \pmod{13}\\ x\equiv 0 \pmod{12}\end{cases}$$ The ...
1
vote
3answers
79 views

Solution congruence system $ x \equiv 11\pmod{36},\,x \equiv 7\pmod{40}, \,x \equiv 32\pmod{75}$

Have solution the following congruence system? $$\begin{align} x & \equiv 11\pmod{36}\\ x & \equiv 7\pmod{40}\\ x & \equiv 32\pmod{75} \end{align}$$ Point of ...
8
votes
4answers
122 views

Show that $15\mid 21n^5 + 10n^3 + 14n$ for all integers $n$.

I'm not sure if it's correct, but what I have so far is; $$21n^5 + 10n^3 + 14n ≡ (1 + 0 - 1) ≡ 0 \mod 5$$ but I'm having trouble solving it in $\bmod 3$. I have: $$21n^5 + 10n^3 + 14n ≡ (0 + (?) + ...