Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [chinese-remainder-theorem]

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

0
votes
2answers
21 views

How to find an element of order 30 in the multiplicative group of $\Bbb Z_{900}$?

I need to find at least one element which has order $30$ in the multiplicative group of $\Bbb Z_{900}$. I'm following this approach but not really understood how to apply correctly the CRT to set the ...
0
votes
1answer
39 views

Problem regarding this proof of Chinese Remainder Theorem

I am facing problem in understanding the last part of the proof of Theorem 6 (Chinese Remainder Theorem. I cannot understand why $(m_j,n_j)=1$. I do not understand the line "Solving $m_j x\equiv 1 (\...
0
votes
2answers
35 views

Is this RSA problem solvable?

A secret message M has been encrypted using the RSA algorithm producing the cyphertext C=12. The public key for the RSA algorithm is e=3, n=51. Compute the decryption component d and hence decipher ...
1
vote
2answers
43 views

Using Chinese Remainder Theorem for large modulo

I'm an undergraduate and currently in a course for abstract algebra. I'm trying to resolve the following problem: Compute which element of $\mathbb{Z}/2550\mathbb{Z}$ under the map of the Chinese ...
1
vote
1answer
39 views

Find all solutions, if any, to the equation $[28][x]-[22] = [33]$ in $\mathbb{Z}_{51}$.

Find all solutions, if any, to the equation $[28][x]-[22] = [33]$ in $\mathbb{Z}_{51}$. I know this simplifies to $[28][x] = [55]$, which can be rewritten as $28x \equiv 55 \bmod{51}$. From ...
3
votes
3answers
49 views

Chinese remainder Theorem in polynomials in one variable.

In a question I was answering, I needed to solve these congruences to proceed, and find the least $k<1000$ $$2k+k^2 = 0 \pmod 3$$ $$ 2k^3 + 6k = 0 \pmod 7$$ $$ k = 0 \pmod 2$$ My try: due to ...
0
votes
0answers
42 views

Chinese remainder theorem and the value of moduli

When we prove the Chinese Remainder Theorem, we construct for the system of linear congruences $$ x \equiv a_1 \mod m_1,\; ... \;,x \equiv a_n \mod m_n$$ we have : $$M_k = \frac{m}{m_k} $$ where m = $...
0
votes
1answer
26 views

Variant of System of linear equation…

Using CRT can we solve: 13925 mod x = y 13811 mod x = 2y 13697 mod x = 3y 13583 mod x = 4y If no, how can this be solved?
2
votes
4answers
44 views

Chinese Remainder Theorem, when the moduli are pairwise coprime.

I'm trying to learn the Chinese Remainder Theorem and I've run into some problem. The problem I am to solve goes like: Find all $x ∈ Z$ such that $x≡2\pmod{3}$ $x≡3\pmod{5}$ $x≡5\pmod{7}$ Also, ...
-1
votes
1answer
30 views

Find all roots of the polynomial $f(x)=x^3-[1]_p$ in $\mathbb{Z}/1729\mathbb{Z}$

Problem is the same as in the title, Find roots of the polynomial $f(x)=x^3-[1]_p$ in $\mathbb{Z}/1729\mathbb{Z}$. I am specifically asking only for someone to point me in the direction of the method ...
3
votes
1answer
54 views

$x^{1682}+22x≡1652 (\bmod3599)$.

Hello I'm trying to learn the Chinese Remainder Theorem and now I have the problem from an old exam: $x^{1682}+22x≡1652 (\bmod3599)$. Ok, so what makes this problem difficult for me is the ...
0
votes
2answers
24 views

Remainders of two integers when divided by another integer n

I am curious if the remainder of u+v is the same as the sum of the two integers separately if they are the same how would one go about proving this
1
vote
1answer
49 views

The Chinese Remainder Theorem with exponentials

Find all $k∈Z_+$ such that: i) $7834^k≡1$ $(mod$ $8613)$ ii) $7834^k≡6850$ $(mod$ $8613)$ iii) $7834^k≡2703$ $(mod$ $8613)$ iv) $7834^k≡1318$ $(mod$ $8613)$ Where $8613=3^3 *11 *29$ Hi I'm ...
2
votes
2answers
57 views

Chinese Remainder Theorem, when the $modulo$-terms are not pairwise coprime.

I'm trying to learn how to use the Chinese Remainder Theorem (CRT), and in order to give some context: We search for all $x ∈ Z$, where $Z$ is the set of integers. $x≡a_1\pmod{m_1}$ $x≡a_2\pmod{m_2}...
1
vote
0answers
24 views

When $\bigcap_{i=1}^n I_i =\prod_{i=1}^n I_i$ for any (noncommutative) ring?

In some thesis there are given ideals $I_i \subset R$ which are pair comaximal and generated by central elements of ring $R$ and it's written "then $\bigcap_{i=1}^n I_i =\prod_{i=1}^n I_i$ for any $n\...
1
vote
0answers
27 views

Proving the surjective property in Chinese Remainder Theorem

If $\textrm{R}$ is a commutative ring and $\left\{\textrm{I}_i\right\}_{i=1}^n$ are proper ideals of $\textrm{R}$ with $\textrm{I}_i+\textrm{I}_j = \textrm{R}$ for all $1 \leq i \neq j \leq n$, then ...
1
vote
2answers
70 views

Simultaneous congruences $3x \equiv 2 \pmod{5}$, $3x \equiv 4 \pmod{7}$, $3x \equiv 6 \pmod{11}$

I am stuck in a simultaneous linear congruence problem: \begin{cases} 3x \equiv 2 \pmod{5} \\[4px] 3x \equiv 4 \pmod{7} \\[4px] 3x \equiv 6 \pmod{11} \end{cases} Using the Chinese remainder theorem, ...
1
vote
3answers
59 views

Chinese remainder theorem, can't figure it out!

x mod 5 = 3 x mod 7 = 5 x mod 11 = 7 How to determine x? I've been searching on YouTube, but they're giving examples in different ways, for example x ≡ 1(mod 3) I don't understand it, is it ...
0
votes
1answer
14 views

System of divisibility constraints

Let us consider integers $a,b$ and $c$ such that all of them are greater than 1. I am trying to figure out whether the following three divisibility conditions can be satisfied together $a|b^{a-1}$ $...
1
vote
2answers
26 views

Find the smallest natural number using Chinese Remainder Theorem

Question is find the smallest natural number x such that, $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 6\ (mod\ 7)$ $x\...
0
votes
1answer
24 views

How to work out modular arithmetic quickly for cryptography [duplicate]

I am not so good at Mathematics so please kindly forgive my stupidity. Basically, I am learning modular arithmetic for cryptography and so I am struggling in understanding how to do big modular ...
0
votes
0answers
64 views

How many solutions does $x \equiv x^{-1} \pmod n$ have?

How many solutions does $x \equiv x^{-1} \pmod n$ have? $n$ is defined to be a positive integer, What I believe the solution will be is along the lines of 2 cases: When $n = 1$, the set of ...
3
votes
3answers
126 views

Some questions about $f: \Bbb Z_{44100} \rightarrow \Bbb Z_{150}\times\Bbb Z_{294}$

Given the function: $f: \Bbb Z_{44100} \rightarrow \Bbb Z_{150}\times\Bbb Z_{294}$ defined as follows $[x]_{44100} \rightarrow ([x]_{150},[x]_{294})$ Calculate $f(12345)$ - Answered A preimage of (...
0
votes
1answer
44 views

Composition of well defined maps is well defined?

If we have two mappings; $a \:mod \:NM \to a \:mod \: M $ and $a \: mod \: NM \to a \:mod \:N $ which are both well defined. Can we then conclude that the mapping $a \: mod \: NM \to (a ...
3
votes
1answer
95 views

Algorithm for finding the smallest integer that satisfies several modular congruence conditions?

my first question! I work a lot with numbers (finance) but very much an amateur mathematician - please be gentle. I have the following problem that has come from discussions about cryptography: Given ...
1
vote
3answers
55 views

System of (non-linear) congruence equations

I got a system of two congruence equations where one of them is non-linear. \begin{cases} 2*x^2 + 5 \equiv 4\ (\textrm{mod}\ 11) \\ x \equiv 3\ (\textrm{mod}\ 13) \end{cases} My idea was to rewrite ...
1
vote
1answer
34 views

exist $x$ such that $x^k \equiv m$ mod $(p_1\cdot p_2) \Leftrightarrow $ exists $x_1,x_2$ : $x_1^k\equiv m(p_1)$ and $x_2^k\equiv m(p_2)$

Let $p_1,p_2$ prime numbers, I wish to show that: exist $x$ such that $x^k \equiv m$ mod $(p_1\cdot p_2) \Leftrightarrow $ exists $x_1,x_2$ : $x_1^k\equiv m(p_1)$ and $x_2^k\equiv m(p_2)$ A first ...
0
votes
3answers
66 views

whats is the remainder when $38^{33^{41}}$ is divided by $11$?

What kind approach is to solve this kind of questions? I have already tried break down and squaring. But still stuck.
1
vote
4answers
63 views

How to solve such a quadratic congruence equation?

I have the following equation: $y^2 \equiv r^2 \pmod n $ I know the values of y and n, I just need to find the values of r. Assuming that $y = 12654$ and $n = 79061$, my working is as follows: $ ...
1
vote
1answer
64 views

$x^2\equiv 5 \pmod{1331p^3}$

Let $p$ be given by $p=2^{89}-1$ and note that it is a Mersenne Prime. The problem is to find the number of incongruent solutions to $$ x^2\equiv 5 \pmod{1331p^3} $$ I began the problem by splitting ...
2
votes
1answer
28 views

Congruence involving CRT

I was working on a problem, I arrived at the point at which I have to find $17^{{{17}^{17}}^{17}} \pmod {25}$ My attempt: $$ 17^{{{17}^{17}}^{17}}\equiv 17^{{{{17}^{17}}^{17}} \pmod{\phi(25)}} \pmod {...
0
votes
1answer
27 views

Derived Chinese Remainder Theorem question

If we know an example of the CRT, e.g.: What $n$ is $3\pmod 7$ and $5\pmod{11}$? and we know the answer, in this case $n=38$, is it any easier to find the answer to a related CRT question, for ...
3
votes
1answer
98 views

The first digit and the last three digits of tower of exponents

How to find the first digit and the last three digits of ${{{{2}^{3}}^{4}}^{\cdots }}^{1000}$, where the expression contains all integer numbers (from $2$ to $1000$, in order)?
1
vote
5answers
62 views

Find the remainder of the division of polynomials

$x^{2007}$ divided by $x^2-x+1$. I consider to solve this problem, should I break the $x^{2007}$ to find the formula $x^2-x+1$?
0
votes
0answers
63 views

Is there a way to reverse the Chinese Remainder Theorem? What extra information do we need?

Dear math stackexchange community, Given a list of numbers < N, after generating the Chinese Remainder, is there a way to get back to the same list of numbers? Example: N = 100 List of numbers =...
0
votes
0answers
33 views

Chinese remainder theorem and Diophantine equation implementation

I needed an advise on implementing and solving one problem and the others like. I came across two sentences that I think will be helpful. Those are the Chinese remainder theorem and the Diofantic ...
0
votes
0answers
36 views

Modular incongruences and Chinese Remainder Theorem

Is there a way to adapt the Chinese remainder theorem to solve a series of modular incongruences, e.g. $n \not\equiv 0\ (\textrm{mod } 5)$ $n \not\equiv 0\ (\textrm{mod } 6)$ $n \not\equiv 0\ (\...
2
votes
0answers
38 views

Remainder for equation with multi-variable

I was trying to figure out the remiander when $(a+b+c)^{333}-a^{333}-b^{333}-c^{333}$ is devided by $(a+b+c)^3-a^3-b^3-c^3$. I first tried to factor them but this guy don't factor in any nice way. I ...
1
vote
4answers
70 views

Proving that $\mathbb{Z}/128\mathbb{Z}$ has exactly one maximal ideal?

I would like the prove that $\mathbb{Z}/128\mathbb{Z}$ has exactly one maximal ideal. I believe this has to do with the fact that $128 = 2^7$, but I'm a little lost on everything else here. I'm ...
0
votes
2answers
68 views

Chinese remainder theorem to find $1030^{989}\bmod\; 3003$?

so this is a slightly different take on a question I asked, but instead of the product of two numbers- this time it is a very large number raised to a very large power. I am meant to use the Chinese ...
0
votes
1answer
62 views

How many elements in $S$ satisfy $x^2=49 \pmod{5400}$?

Let $S=\{0,1,2,...,5399\}$. How many elements in $S$ satisfy $x^2=49 \pmod{5400}$? So I'm thinking about using Chinese remainder Theorem, but since $5400$ has many factors, wouldn't cracking it down ...
1
vote
1answer
33 views

Modular Arithmetic - Solve $a$ and $b$ given equation for $x$

This is an application to the Chinese Remainder Theorem. Given $x=63k+12\ \ \forall k\in\mathbb{Z}$, solve for $a$ and $b$ that satisfy the relation $$x\equiv a \mod7 \\ x\equiv b \mod 9$$ So far ...
0
votes
2answers
85 views

Find all solutions to the system $x \equiv 1 \pmod 4, x \equiv 0 \pmod 3$, and $x \equiv 5 \pmod 7$

Find all solutions to the congruences x $\equiv$ 1 (mod 4), x $\equiv$ 0 (mod 3), and x $\equiv$ 5 (mod 7). I got $M =m_1 * m_2 * m_3 = 4*3*7 = 84$ $M_1 = 21, M_2 = 28, M_3 = 12$ So I get $x = 21*u +...
1
vote
1answer
89 views

Use the Chinese Reminder Theorem to find; (1030 ∗ 989) mod 3003.

I have found a lot of help online for solving a system of congruences but I am not sure what to do with this? I am having a lot of trouble with the Chinese Remainder Theorem in general, but this one ...
0
votes
0answers
14 views

Modular solvability paired quadratic

We have $$B(x+y-L_1)y\equiv Mx\bmod A$$ $$A(x+y-L_2)x\equiv My\bmod B$$ where $A,B$ are known coprime in $[n,2n]$ and $M,L_1,L_2$ are known integers and we have $|x|,|y|<n$. Is there an effective ...
6
votes
1answer
72 views

Validation for a conjecture about Chinese Remainder Theorem for groups

I was wondering if the following statement is true: Let $G$ be a group with normal subgroups $H_1,H_2,...H_n$. Suppose $H_iH_j=G$ for all $i\neq j$. Then $G/H_1\cap H_2...\cap H_n\cong G/H_1 \times......
0
votes
1answer
35 views

Why converted values from Decimal to binary isn't the same? [closed]

the professor told us today about binary and decimal and how to convert them , and give us example of a decimal number (13) and we converted it to binary which is (1101) . Now when I'm trying to do ...
0
votes
1answer
94 views

Chinese Remainder Theorem on polynomials

Let $f(x) = x^5 + 3x^2 + 4$. Find all solution to the congruence. $f(x)\equiv 0 \pmod{12}$. I don't understand how to apply CRT on polynomials.
1
vote
3answers
74 views

How to tell if system of congruences where each base is a power of prime $p$ has a solution

$p$ is a prime number. How to tell if a system of congruences: \begin{align} x &\equiv a_1 \pmod{p^{i_1}} \\ x&\equiv a_2 \pmod{p^{i_2}} \\ &\dots\\ x &\equiv a_n \pmod{p^{i_n}} \...
2
votes
1answer
86 views

Application of Euler's totient function to find last digits

Q:what are the last five digits of the number $2018^{2017^{.^{.^{.^{2^{1}}}}}}$. My Approach:I know how to find the last two digits of $N=2018^{2017^{k}} $ by$N=2018^{2017^{k}\pmod{\phi(25)}}\pmod {25}...