Questions tagged [chinese-remainder-theorem]
For questions related to the Chinese Remainder Theorem and its applications.
0
votes
4answers
42 views
A discrepancy in the proof that 561 is Carmichael number.
The proof is given below:
But I do not understand the statement in the line before last which says "These give rise to the single congruence $a ^{560} \equiv 1 \pmod n$ where gcd(a, 561) = 1 ", I do ...
0
votes
1answer
28 views
A different statement of the Chinese remainder theorem.
My professor gave us a statement for the "Chinese Remainder Theorem" different from that stated in David M. Burton, which say:
If $n_1,\dots,n_k$ are coprime positive integers, then there exist a ...
2
votes
1answer
71 views
The technique that uses the Chinese Remainder theorem, to express 1st order arithmetical statements encoding statements about infinite sets of numbers
I know this technique is heavily used in Number Theory, in Combinatorics (e.g. for phrasing Ramsey's theorems in a first order language of arithmetic), and in some related realms. However, ...
0
votes
0answers
17 views
Application of Chinese Remainder Theorem in a task
Every second I get a remainder $r_i$ by division x $\in \{1, 2, ..., 100\}$ by $a_i$. All $a_i$ are unique, but $a_i$ can be equal to 1. How many pairs of $a_i$ and $r_i$ I need to guess x? This ...
1
vote
0answers
19 views
Reconstruction of Chinese Remainder Theorem without modulo reduction?
Let $a$ be an integer modulo $X = \prod_{i=0}^{k-1}x_i $ where each of $x_i \in \mathbb{Z}$ and for any pair of $i$ and $j$, $x_i$ and $x_j$ are coprime.
Now, using Chinese Remainder Theorem, $a$ is ...
2
votes
1answer
65 views
Congruence equation with power solving method
How can the equation like
$$
x^{118}\equiv 113\;\; (mod\; 1001)
$$
if I know the Fermat's little theorem, Chinese remainder theorem, Euler's theorem and basic operations on congruence?
My approach:
...
1
vote
1answer
27 views
Find two integers with Chinese remainder theorem
Find two intergers having remainders 3, 11, 15 when divided by 10, 13, 17, respectively.
I found one is $1103$. But I'm confused about the other one.
0
votes
1answer
43 views
Prove $a^t$ is congruent to $1$ modulo one of the primes $p,q$ and $-1$ modulo the other prime.
Let $p$ and $q$ be odd primes, and let $N=pq$. Let $t$ be a positive integer such that $a^{2t}\equiv1\pmod{N}$ for all $a\ \epsilon\ (\mathbb Z/N\mathbb Z)^*$, but the congruence $a^t\equiv1\pmod{N}$ ...
-3
votes
1answer
31 views
Please help in solving this [closed]
Find the least two positive integers having the remainders 2, 3, 2 when divided by 3, 5, 7 respectively.
0
votes
1answer
33 views
Chinese remainder theorem and quadratic congruences
By Chinese remainder theorem there is a solution to $x \equiv a_{1} \pmod{ p_{1}}, \ ..., \ x \equiv a_{k} \pmod{ p_{k}}$ if $p_{1}, \ ..., \ p_{k}$ are pairwise coprime and $a_{1}, \ ..., \ a_{k}$ ...
2
votes
2answers
110 views
Adapting the Chinese Remainder Theorem (CRT) for integers to polynomials
I did a few examples using the CRT to solve congruences where everything was in terms of integers. I'm trying to use the same technique for polynomials over $\mathbb{Q}$, but I'm getting stuck.
Here'...
7
votes
5answers
222 views
Remainder theorem for polynomials (JUEE 1990)
Suppose the polynomial $P(x)$ with integer coefficients satisfies the following conditions:
(A) If $P(x)$ is divided by $x^2 − 4x + 3$, the remainder is $65x − 68$.
(B) If $P(x)$ is divided by $x^...
1
vote
0answers
40 views
Chinese Remainder Theorem: Show that $\phi$ is a Ring homomorphism
For an exercise, I need to show that
$$\phi: \mathbb{Z_n} \rightarrow \mathbb{Z_{n_1}} \times \mathbb{Z_{n_2}}; x \mapsto (x\mod n_1, x\mod n_2)$$
where $n = n_1 \cdot n_2$ and $n_1, n_2$ coprime is ...
1
vote
1answer
40 views
Quadratic Congruence modulo square-free integer
If $m$ is a square-free integer, show that $x^{2} + y^{2} \equiv k\pmod{m}$ has a solution $\forall k\in\mathbb{N}$. This means that we need to prove existence of such $m$ for all $k\in\mathbb{N}$.
...
3
votes
1answer
39 views
Solving coupled modular equations over the integers with general coefficients
I have encountered a problem in my research that requires solving two coupled modular equations for integers x,y for general integral coefficients. As someone without much experience in discrete math, ...
0
votes
2answers
71 views
Find the multiplicative inverse of 219 modulo 910 using the Chinese Remainder Theorem.
As $910= 7 \times 10 \times 13,$ I was able to come up with the following system of congruences:
$$2x\equiv 1\mod(7)$$
$$9x\equiv 1\mod(10)$$
$$11x\equiv 1\mod(13)$$
However, I am unsure as to how I ...
0
votes
2answers
53 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
47 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
42 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
53 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
43 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
52 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
49 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
49 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
31 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
60 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
50 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
62 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
34 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
73 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
62 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
15 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
34 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
73 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
136 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
48 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
98 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
62 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
37 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
73 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
68 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
73 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
29 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
105 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
63 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$?
