Questions tagged [chinese-remainder-theorem]
For questions related to the Chinese Remainder Theorem and its applications.
0
votes
0answers
55 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
92 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
39 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
87 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
49 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
27 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
61 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
62 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
47 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
27 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
22 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
91 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
56 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
52 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
31 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
33 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
62 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
64 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
53 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
30 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
63 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
86 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
71 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
33 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
49 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
49 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
71 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}...
0
votes
3answers
32 views
What is the remainder of [closed]
$\dfrac{33^{100}}{50}$
I have done
$\dfrac{2×{33^{100}}}{100}$
But it is still complex. How can we calculate the remainder of a number divided by 100?
0
votes
1answer
39 views
Simple number theory questions (CRT)
I have been watching the Chinese Remainder Theorem, and have some questions about things related to it.
1) I have some questions about the inverse in modular arithmetic. I think that it's easy to ...
0
votes
1answer
34 views
Problem regarding linear congruence
Which of the following statement is False ?
1) There exists a natural number which when divided by 3 leaves remainder 1 and which when divided by 4 leaves remainder 0
2) There exists a natural ...
1
vote
1answer
36 views
Is this a simple LCM or Ad hoc problem or modular arithmetic problem?
I've got a Kindergarten problem, which is to find smallest number which will be satisfied following condition:
If we divide that number with $4, 6$ and $10$ then $2, 4$ and $8$ will be remainder ...
0
votes
0answers
43 views
Chinese remainder theorem in a Dedekind domain.
I want to prove the following :
Let $a_1,...,a_n$ ideals and $x_1,...,x_n$ elements of a Dedekind domain $A$. Then the system of congruences $x \equiv x_i \pmod{a_i}$ for $i = 1,...,n$ has a solution $...
0
votes
1answer
138 views
Computer arithmetic on large integers, (Chinese remainder theorem)
When doing a problem on computer arithmetic with large integers, I reached a step when I needed to solve system of congruences. I came up with the following equations: $$x ≡ 65 \pmod{99})\\
x ≡ ...
3
votes
0answers
17 views
Find $x \in \mathbb{Q}(i)$ with $ |x - 1|_{2+i} < \frac{1}{\sqrt{5}} $, $|x+1|_{2-i} < \frac{1}{\sqrt{5}}$ and $|x|_{7} < \frac{1}{7} $
I wanted to try some examples with adeles and strong aproximation. Let $\mathfrak{p}_1 = 2+i$ and $\mathfrak{p}_2 = 2-i$ and $\mathfrak{p}_3 = 7$. Can we a single number $x \in \mathbb{Q}(i)$ that's ...
3
votes
0answers
42 views
Are we allowed to interchange product and inverse limits?
Currently, I am trying to show that the profinite completion $\hat{\mathbb{Z}}$ of $\mathbb{Z}$ is isomorphic to $\prod_p \mathbb{Z}_p$ (as topological groups) where $p$ runs through all prime numbers ...
2
votes
2answers
73 views
Number theory problem on Chinese remainder theorem
Let $T$ be the smallest positive integer which, when divided by $11,13,15$ leaves remainders in the sets $\{7,8,9\},\{1,2,3\},\{4,5,6\}$ respectively. What is the sum of the squares of the digits of $...
0
votes
0answers
48 views
Chinese remainder theorem - A, B and C think of a code
A, B and C are trying to think of a code. A remembers that after dividing by 13, the residue is 8. its double increased by 1234 after dividing by 17 leaves us residue of 7. C remembers that its triple ...
1
vote
1answer
38 views
Which of the following intervals contains integers satisfying the following three congruences:
Question: Which of the following intervals contains integers satisfying the following three congruences:
$x\equiv 2\pmod 5, x\equiv 3\pmod 7$ and $x\equiv 4\pmod {11}$,
(i) $[401,600]$, (ii) $[601,800]...
0
votes
4answers
117 views
Natural number that has a remainder of $1, 2, 3, 4$ respectively after dividing… [duplicate]
A number when divided by 2 leaves a remainder of 1. When it is divided by 3 leaves a remainder 2. When it is divided by 4 it leaves a remainder of 3. And when it is divided by 5 it leaves remainder of ...
1
vote
2answers
37 views
Linear congruence equations
I'm trying to prove that the following system of congruence equations has a solution:
$X \equiv 2 $ (mod $5^N$)
$X \equiv 1 $ (mod $7^N$)
$X \equiv 4 $ (mod $6^N-4$)
being $N$ an integer number, $...
3
votes
4answers
350 views
Chinese Remainder Theorem: four square roots of 1 modulo N
Given an odd composite number $N$, where $N$ is not a prime power, I read the following in a Wikipedia article:
As a consequence of the Chinese remainder theorem, the number $1$ has at
least four ...
0
votes
4answers
81 views
Solving a system of congruent equations [closed]
1.$$10x\equiv 34 \pmod{63}$$
2.$$11x\equiv 44 \pmod{64}$$
3.$$12x\equiv 54 \pmod{65}$$
How am I supposed to solve it? I know that use of the Chinese remainder theorem is not allowed in this case ...
0
votes
1answer
51 views
Bezout identity on polynomial ring $\Bbb Q[x]$
Question:
After proving that it exists, find $f(x)\in\Bbb Q[x]$ of degree at most 2 such that $$f(x)\equiv2 \text{ mod }x+1\ \text{and }\ f(x)\equiv x+1\text{ mod }x^2+1$$
My attempt:
Since $(x+1)$...
2
votes
1answer
55 views
Remainder of trinomial
What will be the remainder if I divide $(a+b+c)^{333}-a^{333}-b^{333}-c^{333}$ by $(a+b+c)^3-a^3-b^3-c^3$.
I have tried trinomial expention. But its still too big for long division. Is there a shorter ...
2
votes
3answers
63 views
Consider this system of congruence equations.
\begin{cases}
4x \equiv 14 \pmod m \\
3x \equiv 2 \pmod 5
\end{cases}
I want to prove that for $m \in 4\mathbb{Z}$ there are no solutions(1). Moreover, I want to determine all m for which I have ...
-1
votes
2answers
55 views
Modular arithmetic problem from Chinese remainder Theorem
Take $p,q$ to be coprimes with $p<q<2p$. If $w,x,y,z$ are unknowns such that $w,x,y,z<\min(p,q)$ and we know $(wy+xz)\bmod (p+q)$, $(wz+xy)\bmod (p+q)$ $wy\bmod q$ and $xz\bmod p$ then are $w,...
2
votes
1answer
112 views
Chinese Remainder Theorem, Miller-Rabin Primality test, and more…
Good day, I was going over the proof of the Miller-Rabin Primality Test and have a few questions regarding it. THE BOOK IS COMPLEXITY AND CRYPTOGRAPHY: AN INTRODUCTION
Where
$B_t = \{a\in\Bbb Z_n^...
0
votes
1answer
31 views
Direct sum isomorphism question
I found this problem and I'm not sure if I can apply the reminder theorem on it. Are $\mathbb{Z}_8\oplus\mathbb{Z}_{18}$ and $\mathbb{Z}_2\oplus\mathbb{Z}_{72}$ isomorphic? I tend to believe so, but I ...
