number theory

Warning: I have no formal instruction in number theory. (yet)

Let $R(a, b, n)$ be the answer for the common question for $a^b ~\textrm{mod}~ n$ .

$R(4444, 1, 9) = 7$ , since $4444^1 = 4444$ and $4444 ~\textrm{mod}~ 9 = 7$ by the summing digits test

$(ab) ~\textrm{mod}~ n = (a ~\textrm{mod}~ n ) \cdot (b ~\textrm{mod}~ n)$ ,

$4444^b ~\textrm{mod}~ 9 = (4444 ~\textrm{mod}~ 9) \cdot (4444^{b - 1} ~\textrm{mod}~ 9)$

$R(4444,b,9) = (7 \cdot R(4444, b - 1, 9)) ~\textrm{mod}~ 9$

$R(4444, b, 9) = (7 \cdot 7 \cdot 7 \ldots R(4444, 1, 9)) ~\textrm{mod}~ 9$

$R(4444, b, 9) = 7^n ~\textrm{mod}~ 9$

Now that we have something we can actually calculate...

$R(7, 0, 9) = 1$

$R(7, 1, 9) = 7$

$R(7, 2, 9) = 4$

$R(7, 3, 9) = 1$

The pattern repeats 1, 7, 4, 1, 7, 4,... Since 4444 would fall on the third number in the pattern, the answer is 7.

Let $R(a,b,n)$ be the answer for the common question for $a^b$ divided by $n$

$R(4444, 4444,9) = R(4+4+4+4, 4444, 9) = R(7, 4444, 9)$

Since $gcd(7, 9) = 1$ and $\varphi(9) = 6$ ,

$R(7, 4444, 9) = R(7, 4, 9) = \boxed{7}$