7の2019乗の下3桁を求める

下記の動画で取り上げられている問題です。
https://www.youtube.com/watch?v=gtURcnVSAtY

Pythonで計算してみると

>>> 7 ** 2019
179036998645165758896685330687704637285955743317752396970717068338315642795475268763186975478765072330229839303012835249959680095345532400212026753566818982431082409833241973868838699024478742107349472955584411471723559397140304389202860343331445269848637599637468130084737985595066341899725230948749066299955897025147927798637172304922169104713117189269517418621935873673588165426664686315109142724088141992945108734434865411408427647114849943660813768159412189125411762183305685468479155213557196390652674117373410891272834118376420591530930510801922802245921955138767108025846742217167793973571769926457421089144302818420965555350464908841982960590905235504050069076323082792062234848343459293498991617338426927914285191289176975240151581378152737648495304578002685067574431845705493530651365186563383286768062958342095301005279726946499110044794028379817700450355715473328892086594440555284912878689031105026990429004278629814921050471972252097346162817235788599847388876438471670595648076787207402853618107142141275985756292915590208542684159788742057628553337553937872402784655081935632659386220308548728833176626256498584770637988832721911576293410212883389578425986187384691405396588297624275952975884105377342808483490763417407188531991839228520181118974373759771280747325012308067099964433347702444338986586376582750960346447963654934545185524423238522780500080778002642120876263712466026962936597072426623865736538218873264071604206026959939023219238717255006910044653455113440220787437111646885329491879984062540464217620173098416992279757094678234978751692158892952653739759296380028012572681711196731871184819611558197209590003080410428904701313446548140884719437331596380548053346849036973143

>>> str(7 ** 2019)[-3:]
'143'

答は143のようだ。

下3桁は1000で割った余りなので

>>> 7 ** 2019 % 1000
143

これでも求められる。

求め方を工夫してみる。
なにか規則性がないか調べてみる。
7の1乗から7の30乗を1000で割った余りを調べてみる。
下記のPythonのプログラムを使用した。

for i in range(1, 31):
    print(f'7 ** {i} % 1000 = {(7 ** i) % 1000}')

結果

7 ** 1 % 1000 = 7
7 ** 2 % 1000 = 49
7 ** 3 % 1000 = 343
7 ** 4 % 1000 = 401
7 ** 5 % 1000 = 807
7 ** 6 % 1000 = 649
7 ** 7 % 1000 = 543
7 ** 8 % 1000 = 801
7 ** 9 % 1000 = 607
7 ** 10 % 1000 = 249
7 ** 11 % 1000 = 743
7 ** 12 % 1000 = 201
7 ** 13 % 1000 = 407
7 ** 14 % 1000 = 849
7 ** 15 % 1000 = 943
7 ** 16 % 1000 = 601
7 ** 17 % 1000 = 207
7 ** 18 % 1000 = 449
7 ** 19 % 1000 = 143
7 ** 20 % 1000 = 1

7 ** 21 % 1000 = 7
7 ** 22 % 1000 = 49
7 ** 23 % 1000 = 343
7 ** 24 % 1000 = 401
7 ** 25 % 1000 = 807
7 ** 26 % 1000 = 649
7 ** 27 % 1000 = 543
7 ** 28 % 1000 = 801
7 ** 29 % 1000 = 607
7 ** 30 % 1000 = 249

7の1乗から7の20乗までの周期を繰り返すようだ。

あとは、2019乗が1から20までの周期のどれに一致するかを考えればよい。
20の倍数が周期の20番目に一致するので、
2019を20で割った余りの19が周期の番号になる。
したがって、
7 ** 2019 % 1000
= 7 ** (2019 % 20) % 1000
= 7 ** 19 % 1000
= 143

Pythonのプログラムで確認してみる。

for i in range(2001, 2021):
    print(f'7 ** {i} % 1000 = {(7 ** i) % 1000}')

7 ** 2001 % 1000 = 7
7 ** 2002 % 1000 = 49
7 ** 2003 % 1000 = 343
7 ** 2004 % 1000 = 401
7 ** 2005 % 1000 = 807
7 ** 2006 % 1000 = 649
7 ** 2007 % 1000 = 543
7 ** 2008 % 1000 = 801
7 ** 2009 % 1000 = 607
7 ** 2010 % 1000 = 249
7 ** 2011 % 1000 = 743
7 ** 2012 % 1000 = 201
7 ** 2013 % 1000 = 407
7 ** 2014 % 1000 = 849
7 ** 2015 % 1000 = 943
7 ** 2016 % 1000 = 601
7 ** 2017 % 1000 = 207
7 ** 2018 % 1000 = 449
7 ** 2019 % 1000 = 143
7 ** 2020 % 1000 = 1