1
$\begingroup$

I'm trying to find the values of $m^2, m^3, m^4, m^7, (m^3)^7$ modulo 33, for $m$ in $\{0,\dots, 16\}$ and for the values in $\{-16,\dots,0\dots, 16\}$. I'm not entirely sure how to proceed although I do know that I probably have to apply Fermat's Little Theorem in some way (i.e. $m^{32} \equiv 1$ mod 33, $m^{33} \equiv m$ mod 33).

$\endgroup$
  • 1
    $\begingroup$ Hint: $\ m^4 = m^2\,m^2, m^7 = m^4\,m^3\ $, and $\ \left(m^3\right)^7 = \left(m^7\right)^3 = m^7\,m^7\,m^7\ $. $\endgroup$ – lonza leggiera Mar 3 at 9:45
  • $\begingroup$ That's funny, I thought I could get $(m^7)^3=m^{21}=m^{2\lambda(33)+1}$ without first getting $m^7$. $\endgroup$ – Oscar Lanzi Mar 3 at 10:45
  • $\begingroup$ @Oscar Lanzi Yes, of course you can. But since he's been asked to find $\ m^7\ $, then once he's got it he can use it in computing anything else he's been asked to find. As it happens, your proposed method is obviously simpler, since it tells you that $\ m^{21} \equiv m \left(\,\mathrm{mod}\,33\,\right)\ $ at a glance. $\endgroup$ – lonza leggiera Mar 3 at 12:26
1
$\begingroup$

$16^2=32*8=-1*8=25$ mod $33$

$16^3=25*16=50*8=17*8=34*4=1*4$ mod $33$

$16^4=4*16=2*32=-1*2=31$ mod 33

$16^7=16^4*16^3=16^4*4=16^2*32*32=16^2=25$ mod 33

$(16^3)^7=(4)^7=16^3*4=4*4=16$ mod 33

and so on..

You can not use Fermat because 33 is not prime.

$\endgroup$
  • 1
    $\begingroup$ Shouldn't the last line read something like $$(16^3)^7=4^7=(2^7)^2=(4*32)^2=(4*-1)^2=16\ \mathrm{mod}\ 33 $$ $\endgroup$ – lonza leggiera Mar 3 at 12:33
  • $\begingroup$ Thanks you very much $\endgroup$ – Federico Fallucca Mar 3 at 13:40
  • 1
    $\begingroup$ You actually can use fermat, but in parts, by prime factors. $\endgroup$ – Roddy MacPhee Mar 4 at 22:57
  • $\begingroup$ You’re right. He written that $m^32=1$ mod $33$ for all $m$ while it is true if and only if $m$ and $33$ are coprime $\endgroup$ – Federico Fallucca Mar 4 at 23:08
  • $\begingroup$ Using Fermat, and CRT to stitch it together you get m mod 33 for the last,. m mod 3 for the second and fourth, 1 mod 3 for first and third, The hard part is getting those mod 11 values, and CRT. $\endgroup$ – Roddy MacPhee Mar 4 at 23:25
2
$\begingroup$

As well as the hint... lonza leggiera gave in the comments, here are a few more ways to decrease the work:

  • Note $(-x)^{2y}\equiv x^{2y}$, and $(-x)^{2y+1}\equiv-(x)^{2y+1}$.

This allows a rough cutting in half the work needed to calculate the latter ( it's basically negation or not on the first set). This works in any modular arithmetic, because if not, it would defy the normal arithmetic rules:$(-x)^{2y}= x^{2y}$, and $(-x)^{2y+1}= -(x)^{2y+1}$. Thus proving them incorrect.

EDIT: You can Also use Fermat but using prime factorization, Mod 3 they reduce to:

1,m,1,m,and m

if m is coprime to 3. Mod 11 The last can be reduced to m. Using CRT we can piece these together, to get the last is always equal to m mod 33. We have now reduced it to the cases mod 11 and CRT.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.