4
$\begingroup$

Determine the last two digits of: $229^{10}+37^{10}.$ I do not want to use the Euler-totient function or the carmichael function please! Thanks

$\endgroup$
2
  • $\begingroup$ The exponent is small enough to just do the calculation using repeated squaring. $\endgroup$
    – user7530
    Dec 14, 2014 at 5:51
  • $\begingroup$ That is what I did initially, but I felt that there possibly a simpler way not needing as many steps. $\endgroup$
    – Amour
    Dec 14, 2014 at 5:53

4 Answers 4

Reset to default
6
$\begingroup$

Hint:

you can see that $229^{10}=(220+9)^{10}\equiv 9^{10}\equiv729^3\cdot9\equiv29^3\cdot9\equiv 1\pmod{100}$,

also $37^{10}\equiv 7^{10}\equiv49\pmod{100}$,

hence $229^{10}+37^{10}\equiv 50\pmod{100}.$

$\endgroup$
2
  • $\begingroup$ Sorry, how did you simplify (220 + 9)^10 {congruent} 9^10 and then in the next line 37^10 {congruent} 7^10? $\endgroup$
    – Amour
    Dec 14, 2014 at 6:11
  • 2
    $\begingroup$ @AmourK All the binomial coefficients are multiples of 10, except the 1's. $\endgroup$
    – Braindead
    Dec 14, 2014 at 6:12
3
$\begingroup$

Applying binomial theorem, one can rewrite $$ 229^{10}+37^{10} = (230-1)^{10} + (40-3)^{10} \\ =230^{10} - \binom{10}{1}230^9+\binom{10}{2}230^8- \ldots +\binom{10}{8}230^2-\binom{10}{9}230+1\\ +40^{10} - \binom{10}{1}40^9 3+\binom{10}{2}40^8 3^2- \ldots +\binom{10}{8}40^2 3^8-\binom{10}{9}40\cdot 3^9+3^{10}\\ =(......00 -10\cdot230+1)+(.......00-10\cdot40\cdot3^9+3^{10}), $$ so the last two digits of $$229^{10}+37^{10}$$ are the same as the last two digits of $$1^{10}+3^{10}.$$

$\endgroup$
0
$\begingroup$

We need $229^{10}+37^{10}\pmod{100}$

As $100=4\cdot25$ where $(4,25)=1$

$229\equiv1\pmod4\implies229^{10}\equiv1;37\equiv1\pmod4\implies37^{10}\equiv1$

$\implies229^{10}+37^{10}\equiv1+1\pmod4\equiv2\ \ \ \ (1)$

Again, $229\equiv4\pmod{25}\implies229^{10}\equiv4^{10}$

But $4^{10}=(2^2)^{10}=2^{20}$

and $37\equiv12\pmod{25}\equiv2^23\implies37^{10}\equiv(2^23)^{10}\equiv2^{20}3^{10}$

$\implies229^{10}+37^{10}\equiv2^{20}(1+3^{10})\pmod{25}$

Again, $3^3=27\equiv2\pmod{25}\implies3^{10}=3(3^3)^3\equiv3(2)^3\pmod{25}\equiv-1$

$\implies229^{10}+37^{10}\equiv1-1\pmod{25}\equiv0\ \ \ \ (2)$

Now apply Chinese Remainder Theorem on $(1),(2)$

$\endgroup$
0
$\begingroup$

$37^{10}\equiv 7^{10}\equiv 49\pmod{100}$

$229^{10}\equiv 9^{10}\pmod {100}$

$\begin{align}9^3\equiv 29\pmod {100}, 9^2\equiv-19\pmod{100} & \implies 9^5\equiv -(29\cdot19)\pmod{100}\\&\implies 9^5\equiv -551\pmod{100}\\&\implies 9^5\equiv -51\pmod{100}\\&\implies 9^{10}\equiv 1\pmod{100}\end{align}$

$\endgroup$
3
  • 1
    $\begingroup$ The OP wants the last two digits. $\endgroup$
    – user7530
    Dec 14, 2014 at 5:58
  • $\begingroup$ I'm afraid you made mistake in the first line. $229\neq37\times7$ $\endgroup$
    – Mihail
    Dec 15, 2014 at 21:03
  • $\begingroup$ @Mihail: Thanks for noting. It is now edited. $\endgroup$
    – user170039
    Dec 16, 2014 at 4:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .