What is the remainder when 17 100000000 … , with n zeroes is divided by 20? I.e.: 17 10 n mod 20 = ?My approach: I can solve it by Euler's totient function ; 17 8 = 1 mod 20, so remainder is 1.But I want to know if the following method will fetch the result: 17 divided by 20 gives −3 as remainder and −3 raised to any multiple of 10 mod 20 gives 1?Is this logic correct? I think it works only for positive remainder.

Question

What is the remainder when       17          100000000      …      , with   n zeroes is divided by 20? I.e.:      17                  10        n                mod      20  =     ?My approach: I can solve it by Euler&#039;s totient function ;       17    8    =  1    mod      20, so remainder is 1.But I want to know if the following method will fetch the result: 17 divided by 20 gives −3 as remainder and −3 raised to any multiple of   10    mod      20 gives 1?Is this logic correct? I think it works only for positive remainder.

Simon Zhang · Accepted Answer

Modular arithmetic doesn&#039;t care about positive or negative. 17 and −3 behave in exactly the same way modulo 20. They are both representatives of the modulo 20 conjugacy class  {  …  ,  −  23  ,  −  3  ,  17  ,  37  ,  …  }and thus one might even say they are equal, under some interpretations of modular arithmetic (they are equal &quot;in             Z              20      &quot;, for those who know what that means). So yes, that would work.Note that   (  −  3      )    2    =  9  =  10  −  1, so  (  −  3      )    4    =  (  10  −  1      )    2    =  100  −  20  +  1  ≡  1    (  mod    20  )is probably the fastest way to get to your answer.

maredilunavy · Accepted Answer

Hint       gcd  (  a  ,  20  )  =  1    ⇒              x                        4                      ≡    1      (  mod    20  )  ,   being true mod 4 and 5.Thus if         f    n    =      a                            10                                    n                                           then   mod  20    :                       f                  n          +          1                    ≡                                    f            n                                                2                                   by         f          n      +      1        =                    f        n                    10        ≡      (                            f          n                                      2                            )                        4                                        f        n                            2              ≡                    f        n                            2            So                                             n                                0                                1                                2                                3                                ⋯                                                              f              n                                            a                                              a              2                                                          1                                            1                                ⋯                                 by               s      q      u      a      r      i      n      g         repeatedly.

What is the remainder when 17^(100000000…), with n zeroes is divided by 20? I.e.: 17^(10^n)mod20= ?

Answered question

Answer & Explanation

New Questions in Integral Calculus