2
$\begingroup$

Need to use Fermat's Little Theorem (Let $p$ be a prime number and let $a$ be an integer. Then $a^p = a \mod p$. If $p$ does not divide $a$ then $a^p-1 \equiv 1 \mod p$.) $154$ is not prime, but $154 = 22\cdot 7$ and $23$ is prime, so $a^{22} \equiv 1 \mod 23$. $a^{154} \equiv a^{22} \cdot a^7 \equiv 1 \cdot 6 \equiv 6 \mod 23$.

Not sure how to proceed further. Would be grateful for any help.

2 Answers 2

4

You solved it! apart from an arithmetic error.

$\displaystyle a^{mn} = (a^{m})^n$, not $\displaystyle a^{m}* a^{n}$ (which is actually $\displaystyle a^{m+n}$)

Also, not sure how you got $a^7 = 6 \mod 23$.

  • 0
    ah yes, very good point. thanks! and i'm not sure if a^7 = 6 mod 23 is correct. i worked it out as 7*4=28 which has a remained of 6 if a^22 = 1 mod 23.2010-10-17
  • 0
    but i guess i don't even need that since i'm actually taking (a^22)^7, which is (1 mod 23)^7 = 1 mod 23. is that correct?2010-10-17
  • 0
    All that shows is that $a^{28} = a^{6} \mod 23$. It seems like you have some confusion in arithmetic of powers. As to your second comment. Yes, that is correct. You solved it :-)2010-10-17
  • 0
    May I just clarify: i need to show that 23 divides a^154 - 1; obviously 23 divides 1 mod 23 (=a^154) but does 23 divide 1?... I'm working on the assumption that 23 has to divide both parts in order for it to divide the sum/subtraction.2010-10-17
  • 0
    @Maths: Saying $x = y \mod 23$ is equivalent to saying that $x-y$ is divisible by $23$.2010-10-17
2

HINT $\rm\ \ a^{22}\ \equiv 1\ \Rightarrow\ a^{22\: N}\ \equiv\ 1^N\ \equiv\ 1\:.\ $ Now put $\rm\ N = 7\:$.