【P=2^(4n+3)+5^(n+2)は11の倍数】

nを自然数とする。

P=2^(4n+3)+5^(n+2)は11の倍数であることを示せ。

P=2^3×(2^4)^n+5^2×5^n

=8×16^n+25×5^n

≡8×5^n+3×5^n

≡11×5^n

≡0

a^(pn+s)+b^(qn+t)はmの倍数を示せという問題を作る。

a^p≡b^q≡c (mod m)

a^s+b^t≡0 (mod m)

を満たすとき、

P=a^(pn+s)+b^(qn+t)はmの倍数である。

実際

P=(a^s)×(a^p)^n+(b^t)×(b^q)^n

≡(a^s)×c^n+(b^t)×c^n

≡(a^s+b^t)×c^n

≡0

a,b,p,q,s,t,mをどう求めるか？

【問題作成の手順】

①a,b,p,qを設定する

②∣a^p-b^q∣の約数をmとする

③a^s+b^t≡0 (mod m)を満たすs.tを求める

複数あるもの場合は1組選ぶ

a,b,mの関係でs,tが存在しない場合もある

【例】

a=2, b=5, p=4, q=1

2^4-5^1=16-5=11→m=11

2^1≡2、5^1≡5

2^2≡4、5^2≡3

2^3≡8、5^3≡4

2^4≡5、5^4≡9

2^5≡-1、5^5≡1

2^6≡-2

2^7≡-4

2^8≡-8

2^9≡6

2^10≡1

(s,t)=(9,1)(3,2)(7,3)(1,4)(5,5)……

複数あるものから1組選ぶ→(s,t)=(3,2)

P=2^(4n+3)+5^(n+2)は11の倍数

n=t-1を代入すると、

P=2^(4t-1)+5^(t+1)と変形できる

【例】

a=5, b=7, p=2, q=1

5^2-7^1=18→m=9

5^1≡5，7^1≡7

5^2≡7，7^2≡4

5^3≡8，7^3≡1

5^4≡4

5^5≡2

5^6≡1

(s,t)=(1,2)(3,3)(5,1)……→(s,t)=(1,2)

P=5^(2n+1)+7^(n+2)は9の倍数

(2024/8/16)

【a^3+b^3=nの問題作成】

a^3+b^3=n=pq

t=a+bとする。

t(t^2-3ab)=pq

t=p→p^2-3ab=q→3ab=p^2-q

→ab=(p^2-q)/3

よって、a+b=p, ab=(p^2-q)/3

a,bは、x^2-px+(p^2-q)/3=0の解

D=p^2-(4/3)×(p^2-q)

=(1/3)×(3p^2-4p^2+4q)

=(4q-p^2)/3が平方数→整数a,bが存在

(4q-p^2)/3=k^2

4q=p^2+3k^2

q=(p^2+3k^2)/4→n=pq

pとkの奇偶は一致

x=(p±k)/2→{a,b}={(p+k)/2, (p-k)/2}

===============================

奇偶が一致するpとkを設定する。

q=(p^2+3k^2)/4とすれば、

a^3+b^3=pqが整数解(a,b)を持つ。

→{a,b}={(p+k)/2, (p-k)/2}

===============================

(※)p＞kのとき、a,b共に自然数になる

【例】

(p,k)=(3,1)→q=(9+3)/4=3

→n=9=2^3+1^3

(p,k)=(2,4)→q=(4+48)/4=13

→n=26=3^3+(-1)^3

①(p,k)=(7,1)→q=(49+3)/4=13

②(p,k)=(1,11)→q=(1+363)/4=91

→n=91

①91=4^3+3^3

②91=6^3+(-5)^3

①(p,k)=(8,10)→q=(64+300)/4=91

②(p,k)=(2,22)→q=(4+1452)/4=364

③(p,k)=(14,2)→q=(196+12)/4=52

→n=728

①728=9^3+(-1)^3

②728=12^3+(-10)^3

③728=8^3+6^3

===============================

a^3+b^3=nを満たす整数(a,b)

n=pq (p≦q)

r=(4q-p^2)/3が平方数k^2

→整数a,bが存在

→{a,b}={(p+k)/2, (p-k)/2}

===============================

【例】a^3+b^3=728を満たす整数(a,b)

a^3+b^3=728=2^3×7×13

(p,q)=(1,728)→r=2911/3

(p,q)=(2,364)→r=1452/3=484=22^2

→{a,b}={(2+22)/2,(2-22)/2}={12,-10}

(p,q)=(4,182)→r=712/3

(p,q)=(7,104)→r=367/3

(p,q)=(8,91)→r=300/3=100=10^2

→{a,b}={(8+10)/2,(8-10)/2}={9,-1}

(p,q)=(13,56)→r=55/3

(p,q)=(14,52)→r=12/3=4=2^2

→{a,b}={(14+2)/2,(14-2)/2}={8,6}

(p,q)=(26,28)→r=-564/3=-188

以上より、

{a,b}={12,-10}{9,-1}{8,6}

【例】a^3-b^3=65を満たす整数(a,b)

【解】

c=-bとする。

a^3+c^3=65=5×13

(p,q)=(1,65)→r=(260-1)/3=259/3

(p,q)=(5,13)→r=(52-25)/3=9=3^2

→{a,c}={4,1}

(a,c)=(4,1)(1,4)

よって、(a,b)=(4,-1)(1,-4)

【例】a^3-b^3=217を満たす自然数(a,b)

c=-bとする。

a^3+c^3=217

a^3+c^3=217=7×31

(p,q)=(1,217)→r=(868-1)/3=289=17^2

→{a,c}={9,-8}

(p,q)=(7,31)→r=(124-49)/3=25=5^2

→{a,c}={6,1}

以上より、{a,c}={9,-8}{6,1}

したがって、

(a,c)=(9,-8)(-8,9)(6,1)(1,6)

(a,b)=(9,8)(-8,-9)(6,-1)(1,-6)

(2024/7/26)

※n＜0のとき、a^3+b^3=n

(-a)^3+(-b)^3=-n

c=-a, d=-b, m=-n＞0とする。

c^3+d^3=mとして、{c,d}を求めて、

{a,b}を求める。

※p＞qのとき

①p≧4のとき、

pq≧4q, p^2＞pqだから

p^2＞pq≧4q

4q-p^2＜0となり、r＜0→平方数でない

②p=3のとき、q＜3→4q＜12となり、

4q-p^2＜12-9=3→r＜1→平方数でない

③p=2のとき、q=1→r=0

a^3+b^3=2=1^3+1^3

以上より、p≦qのみ考える。

【例】タクシー数1729

a^3+b^3=1729=7×13×19

(p,q)=(1, 1729) →r=2305

(p,q)=(7,247)→r=313

(p,q)=(13,133)→r=121=11^2

→{a,b}={12,1}

(p,q)=(19,91)→r=1=1^2

→{a,b}={10,9}

1729=12^2+1^2=10^2+9^2

【京大の問題にチャレンジ③】

【2005年】

a^3-b^3=217を満たす整数(a,b)を求めよ。

【解】

(a-b)^3+3ab(a-b)=217

t=a-bとする。t＞0の整数

t(t^2+3ab)=217=7×31

t=a+b

t^2+3ab=a^2+ab+b^2

=(a+b/2)^2+(3b^2)/4≧0

t＞0

また

tとt^2+3abの大小関係

t^2+3ab-t=a^2+ab+b^2-(a+b)

=a^2+(b-1)a+b^2-b

=a^2+(b-1)a+(b-1)^2/4-(b-1)^2/4+b^2-b

={a+(b-1)/2}^2+(3b^2+2b-1)/4

={a+(b-1)/2}^2+(9b^2+6b-3)/12

={a+(b-1)/2}^2+(3b+1)^2/12-1/4≧-1/4

(t^2-3ab)-t≧-1/4

t≦(t^2-3ab)+1/4

t, t^2-3abは整数だからt≦t^2-3ab

①t=1→1+3ab=217→ab=72

a-b=1,ab=72

b(b+1)=72→b^2+b-72=0→b=-9,8

(a,b)=(-8,-9)(9,8)

②t=7→49+3ab=31→ab=-6

a-b=7,ab=-6

b(b+7)=-6→b^2+7b+6=0→b=-1,-6

(a,b)=(6,-1)(1,-6)

以上より、

(a,b)=(-8,-9)(9,8)(6,-1)(1,-6)

【キャブタクシー数】

n 番目のキャブタクシー数とは、

2つの立方数の和として n 通りに表される最小の正の整数と定義される。

n=2→3^3+4^3=6^3-5^3=91

n=3→6^3+8^3=9^3-1^3

=12^3-10^3=728

6^3+8^3=9^3-1^3から、

6^3-(-1)^3=9^3-8^3=217

a^3-b^3=217→京大の問題

(a,b)=(s,t)が解のとき、(-t,-s)も解

→(a,b)=(6,-1)(9,8),(1,-6)(-8,-9)

【タクシー数】

2つの自然数の立方数の和として n 通りに表される最小の正の整数

1^3+12^3=9^3+10^3=1729を利用すると

12^3-10^3=9^3-1^3=728

「a^3-b^3=728を満たす自然数(a,b)」

という問題ができる。

【おまけ】

a^3+b^3=728を満たす整数(a,b)を求めよ。

【解】

t=a+bとする。

t(t^2-3ab)=728=2^3×7×13

(t^2-3ab)-t=a^2-ab+b^2-a-b

=a^2-(b+1)a+b^2-b

=a^2-(b+1)a+(b+1)^2/4-(b+1)^2/4+b^2-b

={a-(b+1)/2}^2+(3b^2-6b-1)/4

={a-(b+1)/2}^2+{3(b^2-2b+1)-4}/4

={a-(b+1)/2}^2+(3/4)×(b-1)^2-1≧-1

(t^2-3ab)-t≧-1

t≦(t^2-3ab)+1である。

①t=1→1-3ab=728→3ab=-727→✕

②t=2→4-3ab=364→3ab=-360→ab=-120

a+b=2, ab=-120→{a,b}={12,-10}

③t=4→16-3ab=182→3ab=-166→✕

④t=7→49-3ab=108→3ab=-59→✕

⑤t=8→64-3ab=91→3ab=-27→ab=-9

a+b=8, ab=-9→{a,b}={9,-1}

⑥t=13→169-3ab=56→3ab=113→✕

⑦t=14→196-3ab=52→3ab=144→ab=48

a+b=14, ab=48→{a,b}={6,8}

⑧t=26→676-3ab=28→3ab=648

→ab=213

a+b=26, ab=213→x^2-26x+213=0

D=26^2-4×213=676-852＜0→✕

以上より、

12^3+(-10)^3

=9^3+(-1)^3

=6^3+8^3

=728

(2024/7/26)

【余りの計算】

【倍数の判定法】

pは10と互いに素とする。

10x≡1 (mod p)の解を、x≡t (mod p)

a+tb≡0 (mod p)↔10a+b≡0 (mod p)

以前、倍数の判定法を紹介した。

割り切れるがどうかは調べることができるが、余りも知りたいというのが人情である。

==============================

pは10と互いに素とする。

10x≡1 (mod p)の解を、x≡t (mod p)

mを10tで割った商をa、余りをbとする。10t≡1 (mod p)だから

m=10t×a+b≡a+b (mod p)

==============================

【例】

123456を59で割った余り

t=6

12345=6×2057+3より、

123456=60×2057+36≡2057+36≡2093

2093=60×34+53≡87≡28 (mod 59)

【例】

123456を71で割った余り

t=-7

12345=7×1763+4より、

123456=-70×(-1763)+46≡-1717

171=7×24+3→1717=70×24+37より、

-1717=-70×24-37≡24-37

≡-13≡58 (mod 71)

【例】

123456を83で割った余り

t=3×8+1=25

12345=25×493+20より、

123456=250×493+206≡699

699=250×2+199≡201≡35 (mod 83)

【例】

123456を67で割った余り

t=-3×7+1=-20

12345=20×617+5より、

123456=-200×(-617)+56≡-561

-561=-200×2-161≡-159

≡-25≡42 (mod 67)

tが大きくなると、10tで割った商と余りを求めると大変になり、実用的ではないが理論的には面白い。

(2024/7/24)

2024を26で割った余りを求めよ。

【解】

26=2×13

2024≡0 (mod 2)

p=13→t=3+1=4

2024=40×50+24≡74

74=40×1+34≡35≡9 (mod 13)

よって、(連立合同式)

2024≡0 (mod 2)

2024≡9 (mod 13)→2y≡9≡22→y≡11

2024≡22 (mod 26)

==============================

(連立合同式)

nとmは互いに素とする。

x≡a (mod n)→my≡a (mod n)→y≡s

x≡b (mod m)→ny≡b (mod m)→y≡t

x≡ms+nt (mod mn)

==============================

(※)この問題だと実際に割り算した方が早いが、理論的には面白い。

【倍数の判定法Part②おまけ】

【倍数の判定法】

pは10と互いに素とする。

10x≡1 (mod p)の解を、x≡t (mod p)

a+tb≡0 (mod p)↔10a+b≡0 (mod p)

pは、10k±1, 10k±3と分類できる。

①p=10k+1のとき

10x≡1≡1-p≡-10k→x≡-k

②p=10k+3のとき

10x≡1≡1+3p≡30k+10→x≡3k+1

③p=10k-3のとき

10k≡1≡1+3p≡-30k+10→x≡-3k+1

④p=10k-1のとき

10x≡1≡1+p≡10k→x≡k

【例】

p=7→③k=1→x≡-3+1≡-2→t=-2

p=31→①k=3→x≡-3→t=-3

p=43→②k=4→x≡12+1=13≡-30

→t=13 or t=-30

p=59→④k=6→x≡6→t=6

(2024/7/23)