Calculate the last two decimal places of $\displaystyle 3^{57}$. I have no idea how to do this question.

and

Find the integers x and y that solve each of the following equations, or explain why no solution exists

(a) $\displaystyle 1856x + 984y = 4$
(b) $\displaystyle 11111111x + 3333y = 4444$
(c) $\displaystyle 968x + 372y = 4$

(remembering this is in a number theory context)

2. Hello,
Originally Posted by Maccaman
Calculate the last two decimal places of $\displaystyle 3^{57}$. I have no idea how to do this question.
Note that a number with digits $\displaystyle a_ka_{k-1}\dots a_1a_0$ can be written : $\displaystyle (a_ka_{k-1}\dots a_3a_2) \cdot 100+a_1a_0$
The last two decimal places of a number is equal to its congruence modulo 100.
So basically, you're asked to find x in : $\displaystyle 3^{57} \equiv x (\bmod 100)$
For that, use Euler's totient function :
If $\displaystyle \text{gcd}(a,n)=1$, then $\displaystyle a^{\varphi(n)} \equiv 1(\bmod n)$

$\displaystyle 100=2^2 \cdot 5^2 \Rightarrow \varphi(100)=(4-2)(25-5)=40$

Hence $\displaystyle 3^{40} \equiv 1 (\bmod 100)$

$\displaystyle 3^{57}=3^{40+17}=3^{40} \cdot 3^{17} \equiv 3^{17} (\bmod 100)$

I have to think how to deal with this one

Find the integers x and y that solve each of the following equations, or explain why no solution exists

(a) $\displaystyle 1856x + 984y = 4$
Divide by 4 :
$\displaystyle 464x+246y=1$

Bézout's identity tells us :
there exist x and y such that ax+by=1 if and only if a and b are coprime.
Which is obviously not the case here, since 464 and 246 are both even.

Another way to see that x and y don't exist is that the LHS is even and the RHS, 1, is odd.

(b) $\displaystyle 11111111x + 3333y = 4444$
There are 4x2 digits in 11111111 and 4 in 3333 and 4444.
so divide by 1111 :
10001x+3y=4
subtract 3 on each side :
10001x+3(y-1)=1
And this has a solution, since 10001 and 3 are coprime. Use the extended Euclidean algorithm to find x and y' (y'=y-1)

(c) $\displaystyle 968x + 372y = 4$
Divide by 4 :
242x+93y=1
242 and 93 are coprime (because 93=3x31 and none of them divide 242)
Use the extended Euclidean algorithm too.