1

The question asked:

Find the remainder when $19^{273}$ is divided by $12$.

My textbook shows an alternative method to complete this question, using modular arithmetic.

If we let n be any number, such that:

$ 19^{273}$ ≡ $ n^{273}$ (mod 12)

$ 19^3 $ ≡ $n^3$ (mod 12)

$ 6859$ ≡ $7$ (mod 12)

Remainder is $7$

Another example:

$ 3^{2001} $ ≡ $ n^{2001} $ (mod 7)

$($3^3 $)^{667}$ ≡ $($n^3 $)^{667}$ (mod 7)

$ 3^3 $ ≡ 6(mod7) Therefore remainder is 6

Why does this method work ? What is the purpose of n ?

The method I was familiar with was this:

19 ≡ 7 (mod 12)

$ 19^2$ ≡ 1(mod 12)

$ 361^{136} $ ≡ $1^{136}$ ≡ 1(mod 12)

Therefore 1 x 7 ≡ 7 (mod 12) Hence remainder is 7

Bill Dubuque
  • 272,048
Permutron
  • 11
  • 1
    I have no idea what the first method is saying. I would have written $19^{273}\equiv 7^9\equiv 7\pmod {12}$ since $19\equiv 7\pmod {12}$ and $273\equiv 9 \pmod {11}$. – lulu May 23 '21 at 13:57
  • Clearly, they use 1) $19\equiv 7\bmod 12$ and 2) for every $n$ coprime with $12$, we have $n^{273}\equiv n^{273\bmod\varphi{12}$ by Euler's theorem. – Bernard May 23 '21 at 13:58
  • $19^3=6859$ rather than $6858$ – Henry May 23 '21 at 13:59
  • $19\equiv 7 \mod 12$ and $19^2\equiv 1 \mod 12$ and $19^3\equiv 7 \mod 12$, so any odd power of $19$ is $\equiv 7 \mod 12$ and $273$ is odd – Henry May 23 '21 at 14:04
  • by Euler's thm., $19^{\phi(12)}=19^4\equiv1\bmod12$, so $19^{272}\equiv1\bmod12$, so $19^{273}\equiv19^{272}19\equiv19\equiv7\bmod12$ – J. W. Tanner May 23 '21 at 14:34
  • 2
    @lulu: were you saying $\phi(12)=11$?! $12$ is not prime! $19^{285}\not\equiv7^{10}$ though $285\equiv10\bmod11$. Or perhaps you meant $273\equiv9\bmod\color{red}4$ – J. W. Tanner May 23 '21 at 14:39
  • 1
    @J.W.Tanner Ha! Apparently I was. Thanks for pointing out the blunder. I blame it on lack of caffeine. – lulu May 23 '21 at 14:43
  • 1
    You should not accept answers that don't answer your question. This may discourage others from answering your question, – Bill Dubuque May 23 '21 at 16:43
  • 1
    Do you have any more context that might hint what method the author was applying, e.g. are their immediately prior results or examples that might shed more light on their method? – Bill Dubuque May 24 '21 at 18:33
  • Another example has been added to my original post of the method: $ 3^{2001} $ ≡ $ n^{2001} $ (mod 7)

    $($3^3 $)^{667}$ ≡ $($n^3 $)^{667}$ (mod 7)

    $ 3^3 $ ≡ 6(mod7) Therefore remainder is 6

     – Permutron May 25 '21 at 12:40
  • Unfortunately the new example still yields little insight. Which book are you using? – Bill Dubuque Jun 07 '21 at 01:03

0 Answers0