1

What will be the reminder if $23^{23}+ 15^{23}$ is divided by $19$? Someone did this way:

$15/19 = -4$ remainder and $23/19 = 4$ remainder So $(-4^{23}) + (4^{23}) =0$ but i didn't understand it

vadim123
  • 82,796
  • Hint: http://en.wikipedia.org/wiki/Modular_arithmetic – vadim123 May 14 '13 at 19:54
  • 1
    You can think about it this way. You can write 23 as $(19 + 4)$ , so $23^2$ is $(19 + 4)^2 = (19 \cdot [ 19 + 2 \cdot 4 ] + 4 \cdot 4 )$ , which is a multiple of 19 with a remainder of 16. Each time you multiply by 23 again will create a remainder which can be written as a power of 4 ; so, $23^{23}$ is a multiple of 19 with a "remainder" of $(+4)^{23}$ . The same argument for $15 = (19 - 4)$ means that $15^{23}$ is a multiple of 19 with a "remainder" of $(-4)^{23}$ . An odd power of a negative integer is negative, so $(-4)^{23} = -(4^{23})$ and the "remainders" from division by 19 cancel. – colormegone May 14 '13 at 20:07

2 Answers2

1

$$\forall\,\text{prime}\;p\;\wedge\;\forall\,a\in\Bbb Z\;,\;(a,p)=1\implies a^{p-1}=1\pmod p$$

$$23=4\pmod{19}\;\wedge\;23^{19}= 4^{19}=4\pmod{19}\;,\\\;15=-4\pmod{19}\implies 15^{19}=15=-4\pmod {19}$$

Thus (all the following is onde modulo $\,19\,$ ):

$$23^{23}+15^{23}=4^5+(-4)^5=0$$

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
  • Can you elaborate a little please? –  May 14 '13 at 20:54
  • What, for example? $$23^{23}=4^{23}=4^{19}\cdot 4^4=4\cdot 4^4=4^5\pmod{19}$$ say...? – DonAntonio May 14 '13 at 21:27
  • $23=4\pmod{19};\wedge;23^{19}= 4^{19}=4\pmod{19}$ I didn't understand this. Specially what is this ∧ ? –  May 14 '13 at 21:35
  • $\wedge=$ "and" (conjunction) , $,\vee=$ "or" (disjunction) .This are logical connectives and I, and some others, use them are short writings. – DonAntonio May 14 '13 at 21:40
0

We have $23\equiv 4\pmod{19}$ and $15\equiv -4\pmod{19}$. Then for any odd positive integer $n$, we have $23^n\equiv 4^n \pmod{19}$ and $15^n\equiv (-4)^n \equiv (-1)^n4^n\equiv -(4^n)\pmod{19}$.

Add. We get $4^n -4^n\equiv 0 \pmod{19}$.

Added: We don't really need to go to $4$ and $-4$. For note that $23\equiv -15 \pmod{19}$. So if $n$ is any odd integer, then $23^n +15^n\equiv (-15)^n +15^n\equiv -15^n+15^n\equiv 0\pmod{19}$.

And we do not really need congruence notation. For recall that if $n$ is odd, then $a^n+b^n=(a+b)(a^{n-1}-a^{n-2}b+\cdots +b^{n-1}$. Let $a=23$ and $b=15$. We get that $23+15$ divides $23^{23}+15^{23}$. This yields the desired result.

André Nicolas
  • 507,029