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

learn more… | top users | synonyms

3
votes
1answer
38 views

If $n|m$ prove that the natural surjective projection $\pi: \mathbb{Z_m} \rightarrow \mathbb{Z_n}$ is also surjective in units

Not sure if this is the right proof: since $n|m \Rightarrow n \leq m$, then if we factor $m = p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}$, then $n = p_1^{\beta_1}p_2^{\beta_2}\ldots ...
0
votes
3answers
25 views

Does a system om congruence equations have solutions?

I have a system of congruence equations $$ \begin{cases} x \equiv 17 \pmod{15} \\ x \equiv 14 \pmod{33} \end{cases} $$ I need to investigate the system and see if they've got any solutions. I know ...
0
votes
0answers
19 views

Chinese remainder theorem, some questions.

this time I have no task, but some general questions connected with that theorem. This theorem help us to solve the modular system equations, right? But can we determine $x$ from first equation, for ...
0
votes
1answer
34 views

Isomorphism with Euler phi function

Let $m_i > 1$, where $1 ≤ i ≤ n$, be integers, pairwise relatively prime. Let $m = m_1 \cdots m_n$. Let $\phi(m)$ denote the order of the group $(Z/mZ)^×$. The function $\phi : Z_+ → Z_+$ is called ...
-4
votes
2answers
42 views

IF $f(-2)=3$, then what do we know about $\dfrac{f(x)}{x}+2$ [on hold]

IF $f(-2)=3$, then what do we know about $\dfrac{f(x)}{x+2}$ ?
1
vote
0answers
23 views

Chinese Remainder Problem with three equations

Let's consider: $$*\begin{cases} 7x \equiv 2 \mod 5\\ 3x \equiv 2 \mod 4 \\ 5x \equiv 2 \mod 6 \end{cases}$$
0
votes
1answer
22 views

Wrong applying of simple Chinese Remainder Theorem problem

What am I doing wrong? So for the following equations $$ \begin{align} (*) \left\{ \begin{array}{l} 2x\equiv 3\pmod 5 \\ 4x\equiv 2\pmod 6 \\ 3x\equiv 2\pmod 7 \end{array} \right. ...
1
vote
1answer
18 views

Solve for exponent in modular exponentiation

If given that N^x mod C = B How does one solve for x if (x > 1). I did CRT and got 1, so does anyone know what direction I should go?
0
votes
3answers
50 views

How to solve $100^{63}$ mod 63

I am trying to solve this question but not able to figure out how to approach it. $100^{63} \mod\ {63}$ Please help.
1
vote
1answer
31 views

Proof of ideals and the Chinese remainder theorem

Let $I$ and $J$ be ideals of a ring $R$. Prove that the pair of congruences $y\equiv r\,\mathrm{mod}\,I$ and $y\equiv s\,\mathrm{mod}\,J$ has a solution if and only if $r\equiv s\,\mathrm{mod}\,\, ...
0
votes
1answer
31 views

Solving a system of modular power congruences

I have to find the $x$ value such that $x^k \equiv a_1 \pmod n$ and $x^q \equiv a_2 \pmod n$, where $k$, $q$, $a_1$, $a_2$ are known constants and $n$ is any number. Is there a method to find $x$ ...
1
vote
3answers
32 views

Example involving the Chinese Remainder Theorem

I am working on a Number Theory book and I have come across the following problem: (Underwood Dudley 2nd Edition Section 5 Problem 3): Solve the system: x $\equiv 3(mod 5)$ x $\equiv 5(mod7)$ x ...
1
vote
0answers
35 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
43 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
40 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
37 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
29 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
32 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
72 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
52 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
61 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
43 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
91 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
48 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
191 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
42 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
53 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
66 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
50 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
28 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
30 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
64 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
37 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
32 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
74 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
947 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
61 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
37 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
43 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
9 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
41 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
158 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
60 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 ...