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

learn more… | top users | synonyms

0
votes
1answer
22 views

Big-$\mathcal{O}$ notation for CRT and Extended Euclidean Algorithm

I am very unfamiliar with Big-$\mathcal{O}$ run time calculation. I know that for addition the run time is $\mathcal{O}(\log n)$ and for multiplication the run time is $\mathcal{O}(\log^2 n)$. How ...
1
vote
1answer
18 views

Cubic residues over $\mathbb{Z}_{p^2}^{*}$

Definition: $x\in\mathbb{Z}_{n}^{*}$ is a cubic residue if there exists $y\in\mathbb{Z}_{n}^{*}$ s.t. $y^3\equiv x \pmod{n}$. I have been asked to prove (and I already did) that if $n=pq$, ...
3
votes
4answers
51 views

Find a formula for all integers $x$ such that $5x-1$ is divisible by $13$ and $19x-12$ is divisible by $23$

Find a formula for all integers $x$ such that $5x-1$ is divisible by $13$ and $19x-12$ is divisible by $23$. Hello. I am working on a review sheet for my test tomorrow and I am stuck on this ...
0
votes
1answer
17 views

System of congruences with not coprime numbers

I have a system of congruences, for example $ x \equiv 2 \mod 15$ $ x \equiv a \mod 21$ where $a$ is an integer to be determined. I have to find all the values of $a$ for which the system has ...
0
votes
3answers
31 views

Chinese Remainder Theorem Finding the Modulo

Find numbers $t,u,v$ so that $33t+2 = 20u+13 = 29v-1 $ This is a Chinese Remainder Theory problem, but the problem I am having is finding what are the appropriate modulo. I figure it is easiest to ...
2
votes
3answers
30 views

Solutions for a system of congruence equations

I have a system $$ \begin{cases} x \equiv 7 \pmod{15} \\ x \equiv 14 \pmod{33} \end{cases} $$ How can I show that the system does not have any solutions? I know that the first implies that $x = ...
3
votes
1answer
66 views

If $n\mid m$ prove that the canonical surjection $\pi: \mathbb Z_m \rightarrow \mathbb Z_n$ is also surjective on units

Not sure if this is the right proof (i found it online): Since $n\mid m$, if we factor $m = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$, then $n = p_1^{\beta_1}p_2^{\beta_2}\cdots ...
0
votes
3answers
30 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
21 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
37 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 ...
1
vote
0answers
27 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
19 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
52 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
32 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
33 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
35 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
37 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
45 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
47 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
38 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
34 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
35 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
31 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
55 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
92 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
42 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
49 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
194 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
35 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
55 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
24 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
71 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
52 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
32 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
29 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
42 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
76 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
991 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
64 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
38 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 ...