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

learn more… | top users | synonyms

0
votes
0answers
16 views

Can you use chinese remainder theorum to convert hex to dec in your head?

At one time I was able to convert hex to decimal in my head, using a trick I learned in college. I have not used it in years, and forgot how. Does anyone remember how to use the Chinese remainder ...
1
vote
0answers
40 views

Is this an application of the Chinese Remainder Theorem?

I've been having some issues with the following problem for a few days, and I think I might have found the answer, but I'm not quite sure: Problem: Let f(x) be a polynomial with integer coefficients. ...
0
votes
1answer
21 views

No simultaneous solutions (Chinese Remainder Theorem)

a. Show that $x\equiv2\pmod6$ and $x\equiv3\pmod4$ have no simultaneous solutions. If $x\equiv2\pmod6$ then x is even but if $x\equiv3\pmod4$ then x is odd. This is a contradiction, so ...
1
vote
0answers
35 views

Chinese remainder theorem for infinite equations & equations of infinities

The Chinese remainder theorem is a very well-known theorem of arithmetic and algebra. Inspired by the following paper in model theory, Li Rong Yu, Li Bo Luo - The Generalization of the Chinese ...
0
votes
1answer
31 views

A Question Regarding Remainder Theorem

What is the remainder when $x^3 + 3x^2 - x - 2$ is divided by $(x+3)(x+5)$? You have to solve this using the remainder theorem, which states: If $f(x)$ is divided by $(x-p)$, giving a quotient $g(x)$ ...
0
votes
1answer
24 views

Euler-Totient Multiplicative

http://www.oxfordmathcenter.com/drupal7/node/172 By and large, I understand this proof, however I'm struggling to understand how the Chinese remainder theorem implies that there exists some $x \in ...
0
votes
0answers
25 views

CRT Algorithm using InvMod + Undefined

I am trying to implement a modified CRT function in c++ that calls a function called invMod which is simply the inverse modulus function. I am having difficulty randomly generating values while ...
2
votes
1answer
30 views

generalization of chinese remainder

Let $n_1$, $n_2$,...$n_k \in N^{+}$ and $c_1,c_2,..c_k \in Z$. Then the system of linear congurences $x\equiv c_i\pmod {n_i}$ for $i=1,2,..k$ has a solution if and only if $\gcd(n_i,n_j)\mid ...
2
votes
2answers
71 views

What is the remainder when $12^{39} + 14^{39}$ is divided by $676$?

I tried following but then I got stuck $676 = 26*26$ $12^{39} + 14^{39}$ is divisible $26$ for sure since $a^n + b^n$ is divisible by $(a+b)$ when $n$ is odd. But what to do next?
1
vote
1answer
48 views

Chinese remainder theorem for polynomial evaluation

Let $R$ be a euclidean domain, $m_0,\ldots ,m_{k-1}\in R$ be pairwise coprime and $m:=m_0\cdots m_{k-1}$. The Chinese remainder theorem states: $$\varphi:R\to R/(m_0)\times\cdots \times ...
0
votes
3answers
60 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
42 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
89 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
41 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
46 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
187 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
34 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
50 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
83 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
23 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
58 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
46 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
31 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 ...
1
vote
1answer
24 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
29 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.
1
vote
2answers
63 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
29 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
31 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
71 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
736 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
51 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
35 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
38 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
36 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
138 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
58 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
57 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
27 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
78 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
146 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
106 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
71 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
28 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
54 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
43 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
174 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
28 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 ...