Intereting Posts

How to find the modular reduction of a very large number.
How can one prove $\lim \frac{1}{(n!)^{\frac 1 n}} = 0$?
Distribution of $-\log X$ if $X$ is uniform.
algebraic manipulation of differential form
About matrix derivative
Conjecture: the sequence of sums of all consecutive primes contains an infinite number of primes
Ways $S_3$ can act on a set of 4 elements.
Uniform convergence of sequence of convex functions
Hom functor and left exactness
Matrices with rank exactly r as variety
Prove that $\frac{1}{a^3(b+c)}+\frac{1}{b^3(a+c)}+\frac{1}{c^3(a+b)}\ge \frac32$
Isomorphism from $B/IB$ onto $(B/I)$
Prove the integral of $f$ is positive if $f ≥ 0$, $f$ continuous at $x_0$ and $f(x_0)>0$
Given an exact differential; How do you find the function that satisfies the differential?
Unit speed reparametrization of curve

Calculate without a calculator: $$\left [ 3 \right ]^{2014^{2014}}\mod 98$$

I know I have to use Euler’s Theorem. As a hint it says I might need to use the Chinese Remainder theorem too. I know how both of these work theoretically.

For example I can calculate $5^{256} \mod 13$ with Euler’s Theorem.

But these large numbers throw me off, especially the double power of 2014.

- Doubts about a nested exponents modulo n (homework)
- Flaw or no flaw in MS Excel's RNG?
- Solving a congruence without Fermat's little theorem
- Why is this congruence true?
- Show that $15\mid 21n^5 + 10n^3 + 14n$ for all integers $n$.
- If $n\mid m$ prove that the canonical surjection $\pi: \mathbb Z_m \rightarrow \mathbb Z_n$ is also surjective on units

I started of like this for the Chinese Remainder:

$$98 = 2*7^{2}\\

\left [3 \right ]^{2014^{2014}} \mod 2 \\

\left [3 \right ]^{2014^{2014}} \mod 49 \\$$

Now calculate both:

$$\left [3 \right ]^{2014^{2014}\mod \phi_{(2)} = 2} \equiv \left [3 \right ]^{0} \equiv 1 \mod 2$$

That was lucky.

I fail at mod 49.

Applying Euler’s Theorem on 2014^2014 (since ([3]^2014)^2014 seems even more impossible) gives the following:

$$\phi _{(49)} = 42\\

2014 = 47*42+40\\

2014^{2014} = 2014^{42^{47}}*2014^{40}\equiv 2014^{40} \mod 49$$

(That doesn’t really work without a calculator either.)

And what now, applying Euler’s Theorem again doesn’t work, and I can’t do it in my head either.

Is my approach right? Did I do something wrong?

Please point me in the right direction.

I’m also open to entirely different solutions.

- Proving $(A\cup B)\cap(B\cup C)\cap(C\cup A)=(A\cap B)\cup (A\cap C)\cup (B\cap C)$?
- Prove $\sum \binom nk 2^k = 3^n$ using the binomial theorem
- Expression from generators of Special Linear Groups II
- Induction to prove $2n + 3 < 2^n$
- Sum with binomial coefficients: $\sum_{k=0}^{n}{2n\choose 2k}$
- Using generating functions find the sum $1^3 + 2^3 + 3^3 +\dotsb+ n^3$
- How to teach mathematical induction?
- Should you ever stop rolling, THE SEQUEL
- A new combinatorics identity— similar to Catalan number
- Show that a matched set of nodes forms a matroid

It seems you are mixing exponents and base numbers and what is to be calculated modulo $49$, and what is to be calculated modulo $42$. This is, in my opinion, the chief difficulty working with problems like this, and it’s important to use the utmost care that you actually calculate the correct power in the correct modulus.

We want to know $3^{2014^{2014}} \pmod{98}$. Using the chinese remainder theorem, and the fact that the number is obviously odd, we now have left to calculate $3^{2014^{2014}} \pmod{49}$. In order to do that, we use Euler’s theorem and try to figure out $2014^{2014} \pmod{42}$.

First of all, the reduction $2014 \equiv -2 \pmod {42}$ makes this a bit simpler. That means, in order to use Euler’s theorem to calculate the power of $3$ modulo $49$, we don’t need to bother with powers of $2014$ modulo $42$, it’s enough to consider powers of $-2$.

Now, we want $(-2)^{2014} \pmod{42}$. Using the Chinese remainder theorem, we want to know $(-2)^{2014}$ modulo $7$, $3$ and $2$. Modulo $2$ and $3$ are easy, as $(-2)$ is congruent to $0$ and $1$, respectively.

Modulo $7$ we have Euler’s theorem again, with $\phi(7) = 6$ and $2014 = 2010 + 4$, so $(-2)^{2014} \equiv (-2)^4 = 16 \pmod{7}$. We also see that $16 \equiv 1\pmod 3$ and $16\equiv 0\pmod 2$, so we must have $(-2)^{2014} \equiv 16 \pmod{42}$.

Going back to the base, this means that

$$3^{2014^{2014}} \equiv 3^{(-2)^{2014}} \equiv 3^{16} \pmod{49}$$

So all that’s left now is to calculate $3^{16} \pmod{49}$. This might be done by repeated squaring: $3^{16} = (((3^2)^2)^2)^2$. We have

$$

3^{16} = 9^8 = 81^4 \equiv (-17)^4 = 289^2 \equiv (-5)^2 = 25 \pmod{49}

$$

So to get back to the original question, we know that

$$

3^{2014^{2014}} \equiv \cases{1 \pmod 2\\ 25\pmod{49}}

$$

which means that it’s congruent to $25$ modulo $98$.

- Proving that an integer is the $n$ th power
- Who named “Quotient groups”?
- Square and square root and negative numbers
- If a derivative of a continuous function has a limit, must it agree with that limit?
- How $a^{\log_b x} = x^{\log_b a}$?
- Does Kolmogorov 0-1 law apply to every translation invariant event?
- What is the value of $\frac{\sin x}x$ at $x=0$?
- Showing that $\left\langle a,b \mid abab^{-1}\right\rangle \cong \pi_1(K) \cong \left\langle c,d \mid c^2 d^2 \right\rangle$
- Combination of quadratic and arithmetic series
- Proof of the second Bianchi identity
- Boundedness and Cauchy Sequence: Is a bounded sequence such that $\lim(a_{n+1}-a_n)=0$ necessarily Cauchy?
- Are there infinitely many “super-palindromes”?
- Looking for an identity for characteristic polynomial of a matrix to the power of n
- Prove the general arithmetic-geometric mean inequality
- Math Induction Proof: $(1+\frac1n)^n < n$