1. Find integers $x$ and $y$ such that $17x+101y=1\text{.}$

2. Find ${17}^{-1}(\text{mod}101)\text{.}$

1. Using the identity $x^3+y^3=(x+y)(x^2-xy+y^3)\text{,}$ factor $2^{333}+1$ into a product of two integers greater than 1.

2. Using the congruence $2^2\equiv 1(\text{mod}3)\text{,}$ deduce that $2^{232}\equiv 1(\text{mod}3)$ and show that $2^{333}+1$ is a multiple of 3.

1. Solve $7d\equiv 1(\text{mod}30)\text{.}$

2. Suppose you write a message as a number $m(\text{mod}31)\text{.}$ Encrypt $m$ as $m^7(\text{mod}31)\text{.}$ How would you decrypt? (Hint: Decryption is done by raising the ciphertext to a power mod 31. Fermat’s theorem will be useful.)

Solve $5x+2\equiv 3x-7(\text{mod}31)\text{.}$

1. Find all solutions of $12x\equiv 28(\text{mod}236)\text{.}$

2. Find all solutions of $12x\equiv 30(\text{mod}236)\text{.}$

1. Find all solutions of $4x\equiv 20(\text{mod}50)\text{.}$

2. Find all solutions of $4x\equiv 21(\text{mod}50)\text{.}$

1. Let $n\ge 2\text{.}$ Show that if $n$ is composite then $n$ has a prime factor $p\le \sqrt{n}\text{.}$

2. Use the Euclidean algorithm to compute $gcd(30030\text{,}257)\text{.}$

3. Using the result of parts (a) and (b) and the fact that $30030=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\text{,}$ show that 257 is prime. (Remark: This method of computing one gcd, rather than doing several trial divisions (by 2, 3, 5, ...), is often faster for checking whether small primes divide a number.)

Compute $gcd(12345678987654321\text{,}100)\text{.}$

1. Compute $gcd(4883\text{,}4369)\text{.}$

2. Factor 4883 and 4369 into products of primes.

1. What is $gcd(111\text{,}11)$? Using the Extended Euclidean algorithm, find ${11}^{-1}$ mod $111\text{.}$

2. What is $gcd(1111\text{,}11)$? Does ${11}^{-1}$ mod 1111 exist?

3. Find $gcd(x\text{,}11)\text{,}$ where $x$ consists of $n$ repeated 1s. What can you say about ${11}^{-1}$ mod $x$ as a function of $n$?

1. Let $F_1=1\text{,}{F}_2=1\text{,}{F}_{n+1}=F_n+F_{n-1}$ define the Fibonacci numbers $1\text{,}1\text{,}2\text{,}3\text{,}5\text{,}8\text{,}\dots \text{.}$ Use the Euclidean algorithm to compute $gcd(F_n\text{,}{F}_{n-1})$ for all $n\ge 1\text{.}$

2. Find $gcd(11111111\text{,}11111)\text{.}$

3. Let $a=111\cdots 11$ be formed with $F_n$ repeated 1’s and let $b=111\cdots 11$ be formed with $F_{n-1}$ repeated 1’s. Find $gcd(a\text{,}b)\text{.}$ (Hint: Compare your computations in parts (a) and (b).)

Let $n\ge 2\text{.}$ Show that none of the numbers $n!+2\text{,}n!+3\text{,}n!+4\text{,}\dots \text{,}n!+n$ are prime.

1. Let $p$ be prime. Suppose $a$ and $b$ are integers such that $ab\equiv 0(\text{mod}p)\text{.}$ Show that either $a\equiv 0$ or $b\equiv 0(\text{mod}p)\text{.}$

2. Show that if $a\text{,}b\text{,}n$ are integers with $n|ab$ and $gcd(a\text{,}n)=1\text{,}$ then $n|b\text{.}$

Let $p$ be prime.

1. Show that if $x^2\equiv 0(\text{mod}p)\text{,}$ then $x\equiv 0(\text{mod}p)\text{.}$

2. Show that if $k\ge 2\text{,}$ then $x^2\equiv 0(\text{mod}{p}^k)$ has solutions with $x\cancel{\equiv }0(\text{mod}{p}^k)\text{.}$

Let $p\ge 3$ be prime. Show that the only solutions to $x^2\equiv 1(\text{mod}p)$ are $x\equiv \pm 1(\text{mod}p)\text{.}$ (Hint: Apply Exercise 13(a) to $(x+1)(x-1)\text{.}$)

Find $x$ with $x\equiv 3(\text{mod}5)$ and $x\equiv 9(\text{mod}11)\text{.}$

Suppose $x\equiv 2(\text{mod}7)$ and $x\equiv 3(\text{mod}10)\text{.}$ What is $x$ congruent to mod 70?

Find $x$ with $2x\equiv 1(\text{mod}7)$ and $4x\equiv 2(\text{mod}9)\text{.}$ (Hint: Replace $2x\equiv 1(\text{mod}7)$ with $x\equiv a(\text{mod}7)$ for a suitable $a\text{,}$ and similarly for the second congruence.)

A group of people are arranging themselves for a parade. If they line up three to a row, one person is left over. If they line up four to a row, two people are left over, and if they line up five to a row, three people are left over. What is the smallest possible number of people? What is the next smallest number? (Hint: Interpret this problem in terms of the Chinese remainder theorem.)

You want to find $x$ such that when you divide $x$ by each of the numbers from 2 to 10, the remainder is 1. The smallest such $x$ is $x=1\text{.}$ What is the next smallest $x$? (The answer is less than 3000.)

1. Find all four solutions to $x^2\equiv 133(\text{mod}143)\text{.}$ (Note that $143=11\cdot 13\text{.}$)

2. Find all solutions to $x^2\equiv 77(\text{mod}143)\text{.}$ (There are only two solutions in this case. This is because $gcd(77\text{,}143)\ne 1\text{.}$)

You need to compute ${123456789}^{65537}(\text{mod}581859289607)\text{.}$ A friend offers to help: 1 cent for each multiplication mod 581859289607. Your friend is hoping to get more than $650. Describe how you can have the friend do the computation for less than 25 cents. (Note: $65537=2^{16}+1$ is the most commonly used RSA encryption exponent.)

Divide $2^{10203}$ by 101. What is the remainder?

Divide $3^{987654321}$ by 11. What is the remainder?

Find the last 2 digits of ${123}^{562}\text{.}$

Let $p\equiv 3(\text{mod}4)$ be prime. Show that $x^2\equiv -1(\text{mod}p)$ has no solutions. (Hint: Suppose $x$ exists. Raise both sides to the power $(p-1)/2$ and use Fermat’s theorem. Also, $(-1{)}^{(p-1)/2}=-1$ because $(p-1)/2$ is odd.)

Let $p$ be prime. Show that $a^p\equiv a(\text{mod}p)$ for all $a\text{.}$

Let $p$ be prime and let $a$ and $b$ be integers. Show that $(a+b{)}^p\equiv a^p+b^p(\text{mod}p)\text{.}$

1. Evaluate $7^7(\text{mod}4)\text{.}$

2. Use part (a) to find the last digit of $7^{7^7}\text{.}$ (Note: $a^{b^c}$ means $a^{(b^c)}$ since the other possible interpretation would be $(a^b{)}^c=a^{bc}\text{,}$ which is written more easily without a second exponentiation.) (Hint: Use part (a) and the Basic Principle that follows Euler’s Theorem.)

You are told that exactly one of the numbers

is prime and you have one minute to figure out which one. Describe calculations you could do (with software such as MATLAB or Mathematica) that would give you a very good chance of figuring out which number is prime? Do not do the calculations. Do not try to factor the numbers. They do not have any prime factors less than ${10}^9\text{.}$ You may use modular exponentiation, but you may not use commands of the form “IsPrime[n]” or “NextPrime[n].” (See Computer Problem 3 below.)

1. Let $p=7\text{,}$ 13, or 19. Show that $a^{1728}\equiv 1(\text{mod}p)$ for all $a$ with $p\nmid a\text{.}$

2. Let $p=7\text{,}$ 13, or 19. Show that $a^{1729}\equiv a(\text{mod}p)$ for all $a\text{.}$ (Hint: Consider the case $p|a$ separately.)

3. Show that $a^{1729}\equiv a(\text{mod}1729)$ for all $a\text{.}$ Composite numbers $n$ such that $a^n\equiv a(\text{mod}n)$ for all $a$ are called Carmichael numbers. They are rare (561 is another example), but there are infinitely many of them [Alford et al. 2].

1. Show that $2^{10}\equiv 1(\text{mod}11)$ and $2^5\equiv 1(\text{mod}31)\text{.}$

2. Show that $2^{340}\equiv 1(\text{mod}341)\text{.}$

3. Is 341 prime?

1. Let $p$ be prime and let $a\cancel{\equiv }0(\text{mod}p)\text{.}$ Let $b\equiv a^{p-2}(\text{mod}p)\text{.}$ Show that $ab\equiv 1(\text{mod}p)\text{.}$

2. Use the method of part (a) to solve $2x\equiv 1(\text{mod}7)\text{.}$

You are appearing on the Math Superstars Show and, for the final question, you are given a 500-digit number $n$ and are asked to guess whether or not it is prime. You are told that $n$ is either prime or the product of a 200-digit prime and a 300-digit prime. You have one minute, and fortunately you have a computer. How would you make a guess that’s very probably correct? Name any theorems that you are using.

1. Compute $\varphi (d)$ for all of the divisors of $10$ (namely, 1, 2, 5, 10), and find the sum of these $\varphi (d)\text{.}$

2. Repeat part (a) for all of the divisors of 12.

3. Let $n\ge 1\text{.}$ Conjecture the value of $\sum \varphi (d)\text{,}$ where the sum is over the divisors of $n\text{.}$ (This result is proved in many elementary number theory texts.)

Find a number $\alpha$ mod 7 that is a primitive root mod 7 and find a number $\gamma \cancel{\equiv }0(\text{mod}7)$ that is not a primitive root mod 7. Show that $\alpha$ and $\gamma$ have the desired properties.

1. Show that every nonzero congruence class mod 11 is a power of 2, and therefore 2 is a primitive root mod 11.

2. Note that $2^3\equiv 8(\text{mod}11)\text{.}$ Find $x$ such that $8^x\equiv 2(\text{mod}11)\text{.}$ (Hint: What is the inverse of $3(\text{mod}10)$?)

3. Show that every nonzero congruence class mod 11 is a power of 8, and therefore 8 is a primitive root mod 11.

4. Let $p$ be prime and let $\alpha$ be a primitive root mod $p\text{.}$ Let $h\equiv {\alpha }^y(\text{mod}p)$ with $gcd(y\text{,}p-1)=1\text{.}$ Let $xy\equiv 1(\text{mod}p-1)\text{.}$ Show that $h^x\equiv \alpha (\text{mod}p)\text{.}$

5. Let $p$ and $h$ be as in part (d). Show that $h$ is a primitive root mod $p\text{.}$ (Remark: Since there are $\varphi (p-1)$ possibilities for the exponent $x$ in part (d), this yields all of the $\varphi (p-1)$ primitive roots mod $p\text{.}$)

6. Use the method of part (e) to find all primitive roots for $p=13\text{,}$ given that 2 is a primitive root.

It is known that 14 is a primitive root for the prime $p=30000001\text{.}$ Let $b\equiv {14}^{9000000}(\text{mod}p)\text{.}$ (The exponent is $3(p-1)/10\text{.}$)

1. Explain why $b^{10}\equiv 1(\text{mod}p)\text{.}$

2. Explain why $b\cancel{\equiv }1(\text{mod}p)\text{.}$

1. Find the inverse of $\left(\begin{array}{cc}1& 1\\ 6& 1\end{array}\right)(\text{mod}26)\text{.}$

2. Find all values of $b(\text{mod}26)$ such that $\left(\begin{array}{cc}1& 1\\ b& 1\end{array}\right)(\text{mod}26)$ is invertible.

Find the inverse of $\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)(\text{mod}2)\text{.}$

Find all primes $p$ for which $\left(\begin{array}{cc}3& 5\\ 7& 3\end{array}\right)(\text{mod}p)$ is not invertible.

1. Use the Legendre symbol to show that $x^2\equiv 5(\text{mod}19)$ has a solution.

2. Use the method of Section 3.9 to find a solution to $x^2\equiv 5(\text{mod}19)\text{.}$

Use the Legendre symbol to determine which of the following congruences have solutions (each modulus is prime):

1. $X^2\equiv 123(\text{mod}401)$

2. $X^2\equiv 43(\text{mod}179)$

3. $X^2\equiv 1093(\text{mod}65537)$

1. Let $n$ be odd and assume $gcd(a\text{,}n)=1\text{.}$ Show that if $\left({\displaystyle \frac{a}{n}}\right)=-1\text{,}$ then $a$ is not a square mod $n\text{.}$

2. Show that $\left({\displaystyle \frac{3}{35}}\right)=+1\text{.}$

3. Show that 3 is not a square mod 35.

Let $n=15\text{.}$ Show that $\left({\displaystyle \frac{2}{n}}\right)\cancel{\equiv }{2}^{(n-1)/2}(\text{mod }n)\text{.}$

1. Show that $\left({\displaystyle \frac{3}{65537}}\right)=-1\text{.}$

2. Show that $3^{(65537-1)/2}\cancel{\equiv }1(\text{mod }65537)\text{.}$

3. Use the procedure of Exercise 54 to show that 3 is a primitive root mod 65537. (Remark: The same proof shows that 3 is a primitive root for any prime $p\ge 5$ such that $p-1$ is a power of 2. However, there are only six known primes with $p-1$ a power of 2; namely, 2, 3, 5, 17, 257, 65537. They are called Fermat primes.)

1. Show that the only irreducible polynomials in ${\mathbf{Z}}_2[X]$ of degree at most 2 are $X\text{,}$ $X+1\text{,}$ and $X^2+X+1\text{.}$

2. Show that $X^4+X+1$ is irreducible in ${\mathbf{Z}}_2[X]\text{.}$ (Hint: If it factors, it must have at least one factor of degree at most 2.)

3. Show that $X^4\equiv X+1\text{,}{X}^8\equiv X^2+1\text{,}$ and $X^{16}\equiv X(\text{mod}{X}^4+X+1)\text{.}$

4. Show that $X^{15}\equiv 1(\text{mod}{X}^4+X+1)\text{.}$

1. Show that $X^2+1$ is irreducible in ${\mathbf{Z}}_3[X]\text{.}$

2. Find the multiplicative inverse of $1+2X$ in ${\mathbf{Z}}_3[X](\text{mod}{X}^2+1)\text{.}$

Show that the quotients in the Euclidean algorithm for $gcd(a\text{,}b)$ are exactly the numbers $a_0\text{,}{a}_1\text{,}\dots$ that appear in the continued fraction of $a/b\text{.}$

1. Compute several steps of the continued fractions of $\sqrt{3}$ and $\sqrt{7}\text{.}$ Do you notice any patterns? (It can be shown that the $a_i$’s in the continued fraction of every irrational number of the form $a+b\sqrt{d}$ with $a\text{,}b\text{,}d$ rational and $d>0$ eventually become periodic.)

2. For each of $d=3\text{,}7\text{,}$ let $n$ be such that $a_{n+1}=2a_0$ in the continued fraction of $\sqrt{d}\text{.}$ Compute $p_n$ and $q_n$ and show that $x=p_n$ and $y=q_n$ give a solution of what is known as Pell’s equation: $x^2-d{y}^2=1\text{.}$

3. Use the method of part (b) to solve $x^2-19y^2=1\text{.}$

Compute several steps of the continued fraction expansion of $e\text{.}$ Do you notice any patterns? (On the other hand, the continued fraction expansion of $\pi$ seems to be fairly random.)

Compute several steps of the continued fraction expansion of $(1+\sqrt{5})/2$ and compute the corresponding numbers $p_n$ and $q_n$ (defined in Section 3.12). The sequences $p_0\text{,}{p}_1\text{,}{p}_2\text{,}\dots$ and $q_1\text{,}{q}_2\text{,}\dots$ are what famous sequence of numbers?

Let $a$ and $n>1$ be integers with $gcd(a\text{,}n)=1\text{.}$ The order of $a$ mod $n$ is the smallest positive integer $r$ such that $a^r\equiv 1(\text{mod}n)\text{.}$ We denote $r={\text{ord}}_n(a)\text{.}$

1. Show that $r\le \varphi (n)\text{.}$

2. Show that if $m=rk$ is a multiple of $r\text{,}$ then $a^m\equiv 1(\text{mod}n)\text{.}$

3. Suppose $a^t\equiv 1(\text{mod}n)\text{.}$ Write $t=qr+s$ with $0\le s<r$ (this is just division with remainder). Show that $a^s\equiv 1(\text{mod}n)\text{.}$

4. Using the definition of $r$ and the fact that $0\le s<r\text{,}$ show that $s=0$ and therefore $r|t\text{.}$ This, combined with part (b), yields the result that $a^t\equiv 1(\text{mod}n)$ if and only if ${\text{ord}}_n(a)|t\text{.}$

5. Show that ${\text{ord}}_n(a)|\varphi (n)\text{.}$

This exercise will show by example how to use the results of Exercise 53 to prove a number is a primitive root mod a prime $p\text{,}$ once we know the factorization of $p-1\text{.}$ In particular, we’ll show that 7 is a primitive root mod 601. Note that $600=2^3\cdot 3\cdot 5^2\text{.}$

1. Show that if an integer $r<600$ divides 600, then it divides at least one of 300, 200, 120 (these numbers are 600/2, 600/3, and 600/5).

2. Show that if ${\text{ord}}_{601}(7)<600\text{,}$ then it divides one of the numbers 300, 200, 120.

3. A calculation shows that

   $$7^{300}\equiv 600\text{,}{7}^{200}\equiv 576\text{,}{7}^{120}\equiv 423(\text{mod}601)\text{.}$$

   Why can we conclude that ${\text{ord}}_{601}(7)$ does not divide 300, 200, or 120?

4. Show that 7 is a primitive root mod 601.

5. In general, suppose $p$ is a prime and $p-1=q_1^{a_1}\cdots q_s^{a_s}$ is the factorization of $p-1$ into primes. Describe a procedure to check whether a number $\alpha$ is a primitive root mod $p\text{.}$ (Therefore, if we need to find a primitive root mod $p\text{,}$ we can simply use this procedure to test the numbers $\alpha =$2, 3, 5, 6, ... in succession until we find one that is a primitive root.)

We want to find an exponent $k$ such that $3^k\equiv 2(\text{mod}65537)\text{.}$

1. Observe that $2^{32}\equiv 1(\text{mod}65537)\text{,}$ but $2^{16}\cancel{\equiv }1(\text{mod }65537)\text{.}$ It can be shown (Exercise 46) that 3 is a primitive root mod 65537, which implies that $3^n\equiv 1(\text{mod}65537)$ if and only if $65536|n\text{.}$ Use this to show that $2048|k$ but 4096 does not divide $k\text{.}$ (Hint: Raise both sides of $3^k\equiv 2$ to the 16th and to the 32nd powers.)

2. Use the result of part (a) to conclude that there are only 16 possible choices for $k$ that need to be considered. Use this information to determine $k\text{.}$ This problem shows that if $p-1$ has a special structure, for example, a power of 2, then this can be used to avoid exhaustive searches. Therefore, such primes are cryptographically weak. See Exercise 12 in Chapter 10 for a reinterpretation of the present problem.

1. Let $x=b_1{b}_2\dots b_w$ be an integer written in binary (for example, when $x=1011\text{,}$ we have $b_1=1\text{,}{b}_2=0\text{,}{b}_3=1\text{,}{b}_4=1$). Let $y$ and $n$ be integers. Perform the following procedure:

   1. Start with $k=1$ and $s_1=1\text{.}$

   2. If $b_k=1\text{,}$ let $r_k\equiv s_{k}y(\text{mod}n)\text{.}$ If $b_k=0\text{,}$ let $r_k=s_k\text{.}$

   3. Let $s_{k+1}\equiv r_k^2(\text{mod}n)\text{.}$

   4. If $k=w\text{,}$ stop. If $k<w\text{,}$ add 1 to $k$ and go to (2).

   Show that $r_w\equiv y^x(\text{mod}n)\text{.}$

2. Let $x\text{,}$ $y\text{,}$ and $n$ be positive integers. Show that the following procedure computes $y^x(\text{mod}n)\text{.}$

   1. Start with $a=x\text{,}b=1\text{,}c=y\text{.}$

   2. If $a$ is even, let $a=a/2\text{,}$ and let $b=b\text{,}c\equiv c^2(\text{mod}n)\text{.}$

   3. If $a$ is odd, let $a=a-1\text{,}$ and let $b\equiv bc(\text{mod}n)\text{,}c=c\text{.}$

   4. If $a\ne 0\text{,}$ go to step 2.

   5. Output $b\text{.}$

   (Remark: This algorithm is similar to the one in part (a), but it uses the binary bits of $x$ in reverse order.)

Here is how to construct the $x$ guaranteed by the general form of the Chinese remainder theorem. Suppose $m_1\text{,}\dots \text{,}{m}_k$ are integers with $gcd(m_i\text{,}{m}_j)=1$ whenever $i\ne j\text{.}$ Let $a_1\text{,}\dots \text{,}{a}_k$ be integers. Perform the following procedure:

1. For $i=1\text{,}\dots \text{,}k\text{,}$ let $z_i=m_1\cdots m_{i-1}{m}_{i+1}\cdots m_k\text{.}$

2. For $i=1\text{,}\dots \text{,}k\text{,}$ let $y_i\equiv z_i^{-1}(\text{mod}{m}_i)\text{.}$

3. Let $x=a_1{y}_1{z}_1+\cdots +a_k{y}_k{z}_k\text{.}$

Show $x\equiv a_i(\text{mod}{m}_i)$ for all $i\text{.}$

Alice designs a cryptosystem as follows (this system is due to Rabin). She chooses two distinct primes $p$ and $q$ (preferably, both $p$ and $q$ are congruent to 3 mod 4) and keeps them secret. She makes $n=pq$ public. When Bob wants to send Alice a message $m\text{,}$ he computes $x\equiv m^2(\text{mod}n)$ and sends $x$ to Alice. She makes a decryption machine that does the following: When the machine is given a number $x\text{,}$ it computes the square roots of $x\text{mod}n$ since it knows $p$ and $q\text{.}$ There is usually more than one square root. It chooses one at random, and gives it to Alice. When Alice receives $x$ from Bob, she puts it into her machine. If the output from the machine is a meaningful message, she assumes it is the correct message. If it is not meaningful, she puts $x$ into the machine again. She continues until she gets a meaningful message.

1. Why should Alice expect to get a meaningful message fairly soon?

2. If Oscar intercepts $x$ (he already knows $n$), why should it be hard for him to determine the message $m$?

3. If Eve breaks into Alice’s office and thereby is able to try a few chosen-ciphertext attacks on Alice’s decryption machine, how can she determine the factorization of $n$?

This exercise shows that the Euclidean algorithm computes the gcd. Let $a\text{,}b\text{,}{q}_i\text{,}{r}_i$ be as in Subsection 3.1.3.

1. Let $d$ be a common divisor of $a\text{,}b\text{.}$ Show that $d|r_1\text{,}$ and use this to show that $d|r_2\text{.}$

2. Let $d$ be as in (a). Use induction to show that $d|r_i$ for all $i\text{.}$ In particular, $d|r_k\text{,}$ the last nonzero remainder.

3. Use induction to show that $r_k|r_i$ for $1\le i\le k\text{.}$

4. Using the facts that $r_k|r_1$ and $r_k|r_2\text{,}$ show that $r_k|b$ and then $r_k|a\text{.}$ Therefore, $r_k$ is a common divisor of $a\text{,}b\text{.}$

5. Use (b) to show that $r_k\ge d$ for all common divisors $d\text{,}$ and therefore $r_k$ is the greatest common divisor.

Let $p$ and $q$ be distinct primes.

1. Show that among the integers $m$ satisfying $1\le m<pq\text{,}$ there are $q-1$ multiples of $p\text{,}$ and there are $p-1$ multiples of $q\text{.}$

2. Suppose $\gcd (m\text{,}pq)>1.$ Show that $m$ is a multiple of $p$ or a multiple of $q\text{.}$

3. Show that if $1\le m<pq\text{,}$ then $m$ cannot be a multiple of both $p$ and $q\text{.}$

4. Show that the number of integers $m$ with $1\le m<q$ such that $gcd(m\text{,}pq)=1$ is $pq-1-(p-1)-(q-1)=(p-1)(q-1)\text{.}$ (Remark: This proves the formula that $\varphi (pq)=(p-1)(q-1)\text{.}$)

1. Give an example of integers $m\ne n$ with $gcd(m\text{,}n)gt1$ and integers $a\text{,}b$ such that the simultaneous congruences

   $$x\equiv a(\text{mod}m)\text{,}x\equiv b(\text{mod}n)$$

   have no solution.

2. Give an example of integers $m\ne n$ with $\gcd (m\text{,}n)>1$ and integers $a\ne b$ such that the simultaneous congruences

   $$x\equiv a(\text{mod}m)\text{,}x\equiv b(\text{mod}n)$$

   have a solution.