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

learn more… | top users | synonyms

0
votes
3answers
56 views

modules with several powers $x^{y^z}$

I have an assignment(which gives no credit) which I cant solve so I would like to get some help $3^{{1001}^{1002}}\pmod {43}$ (All original numbers were replaced) Our hint was to use the ...
0
votes
2answers
40 views

Count the integers between $20000$ and $30000$ that end in $39$, and end in $33$ in base $4$, and end in $37$ in base $8$

How I can calculate the integers between $20000$ and $30000$ that end in $39$, and end in $33$ in base $4$, and end in $37$ in base $8$. I think that I have to solve the system of congruences: ...
0
votes
1answer
78 views

How to find out a^b^c^… mod m

I would like to calculate: abcd... mod m I know when a is coprime to m then we can easily find out the answer using Euler's totient function. But I wish to know the ideas when a is not coprime to ...
0
votes
1answer
40 views

Remainder theorem for a real polynomial [closed]

A certain polynomial $p(x)\in\mathbb R[x]$, when divided by $x-a$, $x-b$, $x-c$ gives remainders $a$, $b$, $c$, respectively. How can I find the remainder when $p(x)$ is divided by $(x-a)(x-b)(x-c)$ ...
1
vote
1answer
42 views

A different way to solve Chinese remainder theorem

I'm doing my homework about Chinese remainder theorem $x = a_1(\mod n_1)$ $x = a_2(\mod n_2)$ As I know, x can be found by using: $$x=\{\sum_{i=1}^na_iN_i(N_i^{-1}(\mod n_i)) \}(\mod N)$$ with ...
2
votes
2answers
170 views

Chinese Remainder Theorem, redundant information

I want to solve the following system of congruences: $ x \equiv 1 \mod 2 $ $ x \equiv 2 \mod 3 $ $ x \equiv 3 \mod 4 $ $ x \equiv 4 \mod 5 $ $ x \equiv 5 \mod 6 $ $ x \equiv 0 \mod 7 $ I know, ...
1
vote
0answers
41 views

Given $m^2\bmod A$ and $m^2\bmod B$, how do you find $m^2 \bmod AB$?

Given $m^2\bmod A$ and $m^2\bmod B$, how do you find $m^2 \bmod AB$? I'm 99% sure this is an application of the Chinese remainder theorem, although my workings do not quite show how it can be ...
0
votes
1answer
33 views

Find the number of positive integer $a \leq n$ such that $(a,n) = (a+1,n) = 1)

For every positive integer $n$, let $$A_n = \{a \in \mathbb{N} \mid 1 \leq a \leq n \mid gcd(a,n) = gcd(a+1, n) = 1\}$$ Evaluate $\mid A_n\mid$ Assume that $n$ has the factorization ...
1
vote
1answer
42 views

RSA Encryption using Chinese Remainder Theorem and Fermat's Little Theorem

Self-learning RSA encryption, came across this problem and would like help getting a better understanding of it. Already solved 7(a) and 7(b), but need help with number 8. Thanks! Here is my work ...
0
votes
2answers
79 views

Let $f : \mathbb Z\to \mathbb Z/x\mathbb Z \times \mathbb Z/y\mathbb Z$ be the homomorphism defined by $f (n) = (n + xZ, n + yZ)$…

For $x,y \geq 2$, let $f : \mathbb Z\to \mathbb Z/x\mathbb Z \times \mathbb Z/y\mathbb Z$ be the ring homomorphism defined by $f (n) = (n + xZ, n + yZ)$. (i) The kernel $K$ of $f$ is the ideal ...
0
votes
1answer
22 views

$m=17 \cdot 23 = 391$. With an exponent $e=3$ and encrypted word is $c=21$. Decrpyting exponent $d=235$. Find $w$.

Say $m=17 \cdot 23 = 391$. With an exponent $e=3$ and encrypted word is $c=21$. Decrpyting exponent $d=235$. Find $w$, when $w \equiv c^{d} \pmod{m}$. So far I have split it up like this: ...
0
votes
2answers
41 views

Every Artinian ring is isomorphic to a finite direct product of Artinian local rings

I was reading a proof of the above theorem (1.6.7 Theorem) from here, but there was something that confused me. The proof says $R$ has finitely many maximal ideals $M_1, \ldots ,M_r$, and the ...
1
vote
1answer
37 views

How can i prove that a cartesian product is isomorphic to another cartesian product

$\def\<#1>{\left<#1\right>}\def\Z{\mathbb Z}\<\Z_6, \oplus> \times \<\Z_{10},\oplus>$ is isomorphic to $\<\Z_2, \oplus> \times \<\Z_{30}, \oplus>$ i know i have to ...
1
vote
1answer
29 views

Chinese remainder theorem unique solution

If I have two equations such that $$X\equiv a \pmod b\\ X\equiv c \pmod d$$ I can use linear Diophantine Equations to find multiple solutions to X. Can I find multiple solutions using CRT. what if ...
0
votes
1answer
22 views

Multiplicative functions and Chinese remainder theorem

$ p $ is a nonconstant polynomial with integer coefficients.Define the function $\chi_p(n)$ as the number of zeros of $ p $ in $\mathbb{Z}_n$ for $ n > 1 $, and $ \chi_p(1) = 1 $. e.g., consider $ ...
1
vote
2answers
28 views

remainder, quotient problem [closed]

If a number is divided by 2010, the quotient and remainder are equal. Find the sum of all such positive integers.
0
votes
2answers
56 views

What is the remainder after dividing $(177 + 10^{15})^{166}$ by $1003 = 17 \cdot 59$

What is the remainder after dividing $(177 + 10^{15})^{166}$ by $1003 = 17 \cdot 59$? I have made several observations about the problem but I cant see how they lead me to an answer. Observation one: ...
0
votes
1answer
24 views

How to obtain the least non-negative residue, unique solution, using Chinese Remainder Theorem?

We know that using Chinese Remainder Theorem, CRT, for solving a system of linear congruences will give a unique solution $x \pmod {n_1 n_2\cdots n_t}$ where ${n_1,n_2,\ldots,n_t}$ are coprimes. But ...
1
vote
2answers
26 views

Congruency by completing the square

$x^2+x+1\equiv 0\mod 49$ We have the ring isomorphism $\mathbb{Z}/49\mathbb{Z}\to\mathbb{Z}/7\mathbb{Z}\times\mathbb{Z}/7\mathbb{Z}$. Consider $x^2+x+1\equiv 0\mod 7$ I usually solve these ...
1
vote
2answers
66 views

Solving congruency

$x^2+1\equiv 0 \mod 99$ I rearranged the congruency to get $x^2\equiv -1 \mod 99$. We have an isomorphism $\mathbb{Z}/99\mathbb{Z}\to\mathbb{Z}/ 3 ...
8
votes
3answers
620 views

What remainder does 34! leave when divided by 71 ??

What is the remainder of $ \frac{34!}{71} $? Is there an objective way of solving this? I came across a solution which straight away starts by stating that $69!$ mod $71$ equals $1$ and I lost it ...
1
vote
1answer
27 views

Combining results with Chinese remainder theorem - general case

suppose we have a congruence $$ ax^2+bx+c\equiv 0 \mod (p_1\cdot p_2) $$ being $p_1$ and $p_2$ primes - actually it should be possible to extend these considerations to an arbitrary number of primes ...
0
votes
1answer
28 views

Given the gcd(a, b) = 1, prove x = y mod a & x = y mod b iff x = y mod a*b

I am thinking that this is a variation of the Chinese Remainder Theorem as the iff qualifies that this set of equations is not exactly the definition of the Chinese Remainder Theorem, leading me to ...
0
votes
1answer
33 views

Chinese Remainder Theorem, remainder when dividing by a polynomial

I was reading throught this question: Give the remainder of x^100 divided by (x-2)(x-1) and I couldn't get the same expression as the answers. I have a basic understanding of modulos and Chinese ...
0
votes
1answer
8 views

Congruent question with multiple congruence conditions?

Say if x ≡ 3 (mod 7) and y ≡ 5 (mod 7) How would I use the above given information to solve the problems below? xy ≡ 4 (mod 7) x ≡ y (mod 7) If you could explain it, that would be greatly ...
2
votes
1answer
34 views

Euclidean Algorithm for Modular Inverse, with negative numbers

I might be on to something quite simple which I'm failing to see, while calculating modular inverses. For example, calculating 7x = 5 (mod 12) Which is the same as saying: 7x - 5 = 12k Which ...
1
vote
1answer
100 views

How to count soldiers in the army using Chinese Remainder Theorem?

You are a chinese general and you want to count your army. Your estimate is 790,000 - 810,000. Propose the counting to determine the result unambiguously. The soldiers can only count from to 1 to 12. ...
2
votes
2answers
56 views

Last step of the proof of the Chinese remainder theorem.

For the Chinese Remainder Theorem for rings we have: $$ A/(I\cap J) \cong A/I\times A/J $$ So far I have proven that there is a ring homomorphism from $\phi :A \rightarrow A/I\times A/J $ and the ...
1
vote
2answers
56 views

Chinese remainder theorem?

In the 2014 AIME 1, number 8 says: The positive integers $N$ and $N^2$ both end in the same sequence of four digits $abcd$ when written in base 10, where digit $a$ is not zero. Find the three-digit ...
1
vote
0answers
26 views

Mistake involving Chinese remainder theorem

I ran into a snag in attempting to solve the following problem. $$x\equiv r\pmod p$$ $$x\equiv0\pmod q$$ I did the following $$x=k_1q=k_2p+r$$ $$k_1q\equiv r\pmod p$$ $$k_1\equiv rq^{-1}\pmod p$$ ...
1
vote
2answers
70 views

Easy linear combinations problem.

A small gear with 17 teeth is meshed into a large gear with 60 teeth. The large gear starts rotating at one revolution per minute. How long will it take until the small gear is back to its original ...
1
vote
2answers
90 views

Find all solutions, if any, to the system of congruences x ≡ 7 (mod 9), x ≡ 4 (mod 12), and x ≡ 16 (mod 21)

Using the Chinese Remainder Theorem: $$m=9\cdot21\cdot12=2268$$ $$M_1=\frac{2268}{9}=252, \space M_2=\frac{2268}{12}=189, \space M_3=\frac{2268}{21}=108$$ but when trying to find the inverse: ...
1
vote
3answers
84 views

Prove that if a, b are relatively prime integers, then $\Bbb{Z}/ab\Bbb{Z}$ is isomorphic to $\mathbb{Z}/a\Bbb{Z} \times \Bbb{Z}/b\Bbb{Z}$.

I know this is related to the Chinese remainder theorem but I'm having trouble showing there is an isomorphism between the mapping $\mathbb{Z}/ab\mathbb{Z}$ to $\mathbb{Z}/a\mathbb{Z} \times ...
2
votes
1answer
66 views

Combining results with Chinese Remainder Theorem?

$9x^2 + 27x + 27 \equiv 0 \pmod{21}$ What is the "correct" way to solve this using the Chinese Remainder Theorem? How do I correctly solve this modulo $3$ and modulo $7$ without brute force?
0
votes
1answer
22 views

How can I get the smallest possible answer with the Chinese Remainder Theorem?

I've written some code that takes two integer arrays (one of moduli and one of remainders) and returns a number that solves this set of congruences. It's working, but it's not giving me the smallest ...
1
vote
0answers
53 views

Rigorous proof writing

I'm a little bit confused about this problem "Suppose that $m_1, m_2, ..., m_r$ are pairwise relatively prime positive integers. For each j, let $C(m_j)$ denote a complete system of residues mod ...
0
votes
1answer
32 views

Consecutive numbers and Chinese remainder theorem [closed]

Prove that there exists a sequence of 100 consecutive numbers, that each one of them can be divided by a multiplication of 2 different primes. The hint to this question was to use Chinese ...
1
vote
1answer
130 views

Calculating powers of large number using Chinese Remainder Theorem

Supposed we want to calculate the power of: $2^{99999999999999} + 6^{567563535463455555}$ and we have a set of prime numbers $\{x : x \in\mathbb{Z}, \text{ isPrime}(x)\}$ Now its obvious that trying ...
0
votes
2answers
25 views

Finding the inverse of a congruence

I am studying Chinese Remainder Theorem in my Information Theory class. It involves solving congruences. All I know about congruences is what I learned from ...
0
votes
0answers
27 views

Proving Chinese number theorem problem

Assume the following $$q \equiv m \pmod{x} \\ q \equiv n \pmod{y}$$ Show the following where $q$ doesnt go to $(m,n)$ $$q = (my(y^{-1} \bmod{x}) + nx(x^{-1} \bmod{y})\bmod{xy}$$ Breaking it down ...
0
votes
0answers
43 views

Chinese Number Theorem w/ extended Euclidean Algorithm

I am given the following: 153 = x^3 mod 155 196 = x^3 mod 203 27 = x^3 mod 117 My first thought was that I could turn this into an equivalence and say ...
4
votes
1answer
38 views

Solve congruence $8x \equiv 28 \mod30 , 11x \equiv 1 \mod35$

I need to solve the following set of congruences. \begin{cases} 8x \equiv 28 & \mod30 \\ 11x \equiv 1 & \mod35\end{cases} Finding the inverse of $11$ in the ring $\mathbb{Z}_{35}$ led to ...
1
vote
1answer
59 views

Chinese remainder theorem with squares

I have to solve a Chinese remainder theorem example where one of the congruence relations is $x^2 = 1 (4)$. I figured out that it should also be possible to write $x=1(2)$. Is this correct and is ...
1
vote
1answer
24 views

Find the value of k

Find the value of k if $(3x + k)^3 + (4x - 7)^2$ has a remainder of $33$ when divided by $x-3$ Should I split up the main equation: $(3x + k)^3 + (4x - 7)^2$ ?
0
votes
3answers
98 views

Question on application of Chinese Remainder Theorem

$$x\; ≡\; 3\; \left( \mbox{mod}\; 30 \right)$$ $$x\; ≡\; 5\; \left( \mbox{mod}\; 56 \right)$$ I have a system of modular equation that I want to solve. However, I thought that this system has no ...
1
vote
1answer
31 views

Help understand lecturers example

My lecture gave us the following example and I am having trouble following it Would √23(mod 209) not become √23(mod 11) and √23(mod 19)? How is he getting √4? And also I do not know how to use the ...
2
votes
2answers
60 views

system of congruences proof

I've checked a lot of the congruency posts and haven't seen this one yet, so I'm going to ask it. If there is a related one, I'd be happy to see it. Let $x \equiv r\pmod{m}, x \equiv s\pmod{(m+1)}$. ...
4
votes
5answers
383 views

Chinese Remainder Theorem clarification

So I have been trying to understand the Chinese Remainder Theorem for some time now and I just don't know what is going on. I have looked at the definition many times and I understand congruence ...
2
votes
2answers
66 views

square of primes above 5

Given that squares of all primes above 5 are either 1 (mod 30) or 19 (mod 30), is this just a curious coincidence, or is there some straight-forward explanation? My research has not lead me to any ...
2
votes
2answers
185 views

Chinese Remainder Theorem Explanation

I'm reading through a brief example of the Chinese remainder theorem and am having difficulty understand the process they are going through. Consider two primes p and q. For an arbitrary a < p and ...