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

learn more… | top users | synonyms

1
vote
4answers
29 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
28 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
58 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
11 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
25 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
49 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
41 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
63 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
81 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
72 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
50 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
148 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
43 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
246 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
23 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
35 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
98 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
57 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
94 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
42 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
55 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
95 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
41 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
54 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
34 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
25 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
4answers
38 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
76 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
121 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 + (?) + ...
1
vote
2answers
64 views

If every pair of congruence equations admits solutions, then the entire system admits solutions

Let a system of three linear congruence equations in integers be given; \begin{cases}x\equiv b_1\mod c_1\\ x\equiv b_2\mod c_2\\ x\equiv b_3\mod c_3\\ \end{cases} with $c_1,c_2,c_3\in\mathbb ...
0
votes
3answers
47 views

Solving a system of congruences using the Chinese Remainder Theorem

Suppose I have the congruences: $x \equiv 3 ($mod $7)$ $x \equiv 8 ($mod $9)$ $x \equiv 1 ($mod $5)$ $x \equiv 1($mod $16)$ The Chinese Remainder Theorem says I will have a solution $($mod ...
1
vote
1answer
33 views

Using CRT to prove a single congruence relation

I am trying to prove that $2^{700} \equiv 1 \mod 3625$ and I am supposed to use the Chinese Remainder Theorem as part of my proof. I know that the Chinese Remainder Theorem tells me that a solution ...
-1
votes
1answer
61 views

Does $x^2=83\pmod{101}$ have solutions? without calculating them

Does $x^2=83\pmod{101}$ have solutions? without calculating them. I'm not sure how to tackle this without solving, I tried using chinese remainder and quadratic reciprocity.
1
vote
1answer
38 views

Non-linear congruence equation

I want to find solutions to the equation $x^3 + 2x - 3 \equiv 0 (mod 45)$. I have already found solutions to $x^3 + 2x - 3 \equiv 0 (mod 5)$ and $x^3 + 2x - 3 \equiv 0 (mod 9)$, simply by brute ...
4
votes
2answers
205 views

Converse to Chinese Remainder Theorem

So as seen on this question Converse of the Chinese Remainder Theorem, we know that if $(n,m) \neq 1$, then $\mathbb{Z} /mn \mathbb{Z} \ncong \mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/m\mathbb{Z}$, ...
2
votes
3answers
53 views

How to find all solutions to system of congruences with Chinese Remainder Theorem?

This is from Discrete Mathematics and its Applications Here is my work so far gcd(3, 4) = 1 $\,$gcd(3, 5) = 1$\,$gcd(4,5) = 1 $\quad$ mod 3 $\quad$ mod 4 $\quad$mod 5 x $\equiv$ 4 * 5$\qquad$3 * ...
1
vote
1answer
36 views

Why doesn't the author straight up multiply the 15 by 2 in Chinese Remainder Theorem?

This is from a Youtube video on the Chinese Remainder Theorem -https://www.youtube.com/watch?v=ru7mWZJlRQg The value at each column is the product of the mod of the two other columns(so moding will ...
2
votes
1answer
44 views

Why doesn't the author subtract everything by two first before applying modulus?

This is from a youtube video on the Chinese Remainder Theorem - https://www.youtube.com/watch?v=ru7mWZJlRQg What the author has done thus far is basically 1.Make sure that the mods, 3, 4, 5 are ...
2
votes
1answer
41 views

Number Theory: Let $m = 2^ap_1^{b_1}p_2^{b_2}…p_r^{b_r}$ where $a\geq 0,r \geq 0, b_i \geq 1$.

I need to find how many incongruent solutions exist to the equation: $x^2 \equiv 1(mod\space m)$. I'm thinking I need to take a case by case approach, for example when $a = 0$, but these number ...
1
vote
0answers
15 views

$x ≡ a \pmod{m}, x ≡ b\pmod{n}, x ≡ c\pmod{r}$ [duplicate]

What could be an example of three positive integers $m, n$, and $r$, and three integers $a, b$, and $c$ such that the $\mathrm{gcd}$ of $m, n$, and $r$ is $1$, but there is no simultaneous solution to ...
0
votes
2answers
40 views

Chinese Remainder Theorem for non prime-numbers.

Let's say I want to find x such that x leaves remainder 2 when divided by 3 and x leaves remainder 3 when divided by 5. x % 3 = 2 x % 5 = 3 We break down the problem to: x % 3 = 1 x % 5 = 0 ...
1
vote
1answer
84 views

very hard question using chinese remainder theorem

Q. let $p$ and $q$ be distinct odd prime numbers. Prove that for any $x \in \mathbb{Z} /pq$ we get $$x^{(pq-p-q+3)/2} \equiv x \mod pq$$ we have just learnt the chinese remainder theorem so I have ...
3
votes
4answers
76 views

Solving modulus equation systems

I am studying for a test in discrete math and I created my own question but I cannot seem to solve it. Is it possible to solve the following equation system (without brainless testing), and if so, ...
1
vote
2answers
85 views

System of congruences and Chinese remainder theorem

Find all the integers satisfying this system of congruences $$\begin{cases} x \equiv 2 \pmod 5\\ x \equiv 1 \pmod {10}\\ x \equiv 0 \pmod 3 \end{cases} $$ I think you use Chinese remainder theorem ...
2
votes
0answers
50 views

Chinese Remainder Theorem with with non-pairwise coprime moduli

I have a system of congruences: $$ x\equiv 1\pmod 2 \\ x\equiv 2\pmod 3 \\ x\equiv 3\pmod 4 \\ x\equiv 4\pmod 5 \\ x\equiv 5\pmod 6 \\ x\equiv 0\pmod 7 $$ 2, 3, 4, 5, 6, 7 are non-pairwise coprime, ...