Evaluate $gcd(8765\text{,}23485)\text{.}$

1. Find integers $x$ and $y$ with $65537x+3511y=1\text{.}$

2. Find integers $x$ and $y$ with $65537x+3511y=17\text{.}$

You are told that exactly one of the numbers

is prime and you have one minute to figure out which one. 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].” (This makes explicit Exercise 30 above.)

Find the last five digits of $3^{1234567}\text{.}$ (Note: Don’t ask the computer to print $3^{1234567}\text{.}$ It is too large!)

Look at the decimal expansion of $e=2.71828182845904523\dots \text{.}$ Find the consecutive digits 71, the consecutive digits 271, and the consecutive digits 4523 form primes. Find the first set of five consecutive digits that form a prime ($04523$ does not count as a five-digit number).

Solve $314x\equiv 271(\text{mod}11111)\text{.}$

Find all solutions to $216x\equiv 66(\text{mod}606)\text{.}$

Find an integer such that when it is divided by 101 the remainder is 17, when it is divided by 201 the remainder is 18, and when it is divided by 301 the remainder is 19.

Let $n=391=17\cdot 23\text{.}$ Show that $2^{n-1}\cancel{\equiv }1(\text{mod}n)\text{.}$ Find an exponent $j>0$ such that $2^j\equiv 1(\text{mod}n)\text{.}$

Let $n=84047\cdot 65497\text{.}$ Find $x$ and $y$ with $x^2\equiv y^2(\text{mod}n)$ but $x\cancel{\equiv }\pm y(\text{mod}n)\text{.}$

Let $M=\left(\begin{array}{ccc}1& 2& 4\\ 1& 5& 25\\ 1& 14& 196\end{array}\right)\text{.}$

1. Find the inverse of $M(\text{mod}101)\text{.}$

2. For which primes $p$ does $M$ not have an inverse mod $p$?

Find the square roots of 26055 mod the prime 34807.

Find all square roots of 1522756 mod 2325781.

Try to find a square root of 48382 mod the prime 83987, using the method of Section 3.9. Square your answer to see if it is correct. What number did you find the square root of?