19718：３以上の奇数a, a^2-aが10000で割り切れるものは？

問題19718・・・http://hibiyastudy.hatenablog.com/entry/math/problems/02 より 引用 Orz〜

3以上9999以下の奇数aで、a2-aが10000で割り切れるものを1つ求めよ。

解答

・わたしの...

a(a-1) なので、a-1は偶数

10000=2^4*5^4

5^4=625

624*625=390000

(100m+624)(100m+625)

≡100m(624+625)

1249m≡0 (mod 100)

100m>10^4 なので、他にはないですね ^^

・鍵コメY様からのインフォ頂戴 Orz〜

https://okayadokary.blog.fc2.com/blog-entry-223.html
https://blogs.yahoo.co.jp/crazy_tombo/50538626.html ;

*前回、下３桁が累乗{(ABC)^2,(ABC)^3,...}でも変わらない数ABCを求める問題で参照願ったサイトです ^^

下何桁でも求まる一般的な方法が披瀝されています☆

・鍵コメT様からのもの Orz〜

625が結論であり，「他にない」も正しいのですが，
他にないことを示すのに
「100m+625」の形の数を調べるのではまずいと思います．
(実際，a^2-aが10000の倍数となる奇数aで625の次のものは10001です．)

a^2-a=a(a-1)であり，a,a-1は互いに素だから，
積が10000で割り切れるとき，一方は2^4の倍数，一方は5^4の倍数．
3≦a≦9999より，aもa-1も両方の倍数とはなり得ない．
aが奇数であることから，aは625の倍数，a-1は16の倍数．
16a≡0 (mod 10000)，625a≡625 (mod 10000)であり，
16,625が互いに素であることから，
これを満たすaは，a≡k (mod 10000)の形でkが1つに定まる．
よって，解はa=625のみ．

*後半の詳説頂戴 Orz〜

まず，aが625の倍数であることは，a≡0 (mod 625)と表され，
合同式の両辺および法に0以外の同じ整数をかけることは同値変形なので，
これは16a≡0 (mod 10000)…[1]と変形できます．
「a-1は16の倍数」も同様に，a≡1 (mod 16)から，
625a≡625 (mod 10000)…[2]とできます．
さて，問題15821で，合同式の1次方程式の解き方を説明しています．
そこでは，「ax≡0 (mod a)」という常に成り立つ式を付け加えることで，
1次方程式をわざわざ連立方程式に変え，
互除法を用いてxの係数を小さくしていったわけですが，
はじめから連立方程式である場合も，同様の手法で解くことができます．
すると，[1],[2]の連立方程式を解いた結果は，
必ず「a≡○ (mod 10000)」という形になることがわかりますね．

また，定理「互いに素である2つの自然数p,qについて，
nをp,qで割った余りが指定されると，nを積pqで割った余りが1つ定まる」
を利用することもできます．
(この定理は「中国の剰余定理」とか「孫子の定理」とか言われる定理で，
検索してみたところ，2016/5/28にスモークマンさんが記事を
アップされているのが見つかりました．(https://blogs.yahoo.co.jp/crazy_tombo/49318508.html 参照)

また，

問題11707(https://blogs.yahoo.co.jp/crazy_tombo/folder/931624.html?m=lc&sv=11707&sk=0)，

問題11892(https://blogs.yahoo.co.jp/crazy_tombo/folder/931624.html?m=lc&sv=11892&sk=0)，

問題15342(https://blogs.yahoo.co.jp/crazy_tombo/folder/931624.html?m=lc&sv=15342&sk=0)，

問題19509(https://blogs.yahoo.co.jp/crazy_tombo/folder/931624.html?m=lc&sv=19509&sk=0)

においては，私のコメントの中で触れられています．)

16と625は互いに素なので，これらで割った余りが定まれば，
10000で割った余りが1つに定まることになります．

*いつもその時は分かったつもりになるのに...すぐピンとこないのは実際にゃ分かってないってことあるね...^^;;;...Orz〜

[スモークマン]

＞7:08pmの鍵コメY様へ ^^
a^2-a≡0 (mod 10000)とは、2乗してしても下4桁が変わらないもので、aが奇数の方ということで、以前出場した常に2種類あるうちの一方だけなので...1個になるというわけですのね ^^v
追記させていただきまっす Orz〜

[スモークマン]

＞8:11pmの鍵コメT様へ ^^
ものすごく基本的な部分だと思われますが...^^;

>16a≡0 (mod 10000)，625a≡625 (mod 10000)であり，
>16,625が互いに素であることから，
>これを満たすaは，a≡k (mod 10000)の形でkが1つに定まる．

というところが理解できてましぇん ^^;; Orz〜

[スモークマン]

＞0:24amの鍵コメT様へ ^^
なるほど♪
懇切丁寧な解説グラッチェ〜^^
紹介させていただきまっす〜m(_ _)m〜v