【余りの計算】

【倍数の判定法】

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)

【倍数の判定Part②】

【倍数の判定法】

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

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

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

【例】7の倍数

10x≡1 (mod 7)

10x≡1+7×(-3)≡-20→x≡-2≡5

a-2b≡0 (mod 7)↔10a+b≡0 (mod 7)

a+5b≡0 (mod 7)↔10a+b≡0 (mod 7)

【例】13の倍数

10x≡1 (mod 13)

10x≡1+13×3≡40→x≡4

a+4b≡0 (mod 13)↔10a+b≡0 (mod 13)

【例】63の倍数

10x≡1 (mod 63)

10x≡1+63×3≡190→x≡19

a+19b≡0 (mod 63)

↔10a+b≡0 (mod 63)

【証明】

pと10は互いに素だから

ps+10t=1を満たす整数(s,t)が存在する

10a+b

=10a+(ps+10t)b=10(a+tb)+psb

よって、

a+tb≡0 (mod p)

↔10a+b≡0 (mod p)

tを考えると、10t≡1 (mod p)

tは、10x≡1 (mod p)の解である。

(2024/7/16)

【例】n=123456は7 の倍数か？

a+5b≡0 (mod 7)↔10a+b≡0 (mod 7)

12345+30=12375

1237+25=1262

126+10=136

13+30=43

n=123456は7の倍数でない。

(※)123456=7×17636+4

a-2b≡0 (mod 7)↔10a+b≡0 (mod 7)

を利用してもOK

【例】n=122667は31の倍数か？

10x≡1 (mod 31)

10x≡1-31≡-30→x≡-3

a-3b≡0 (mod 31)↔10a+b≡0 (mod 31)

12266-21=12245

1224-15=1209

120-27=93

9-9=0

n=122667は31の倍数である。

(※)122667=31×3957

【例】2021は43の倍数か？

10x≡1 (mod 43)

10x≡1+43×3≡130→x≡13≡-30

a+13b≡0↔10a+b≡0↔a-30b≡0

2021→202+13=215→21+65=86=43×2

2021→202-30=172→17-60=-43

2021は43 の倍数

(※)2021=43×47

計算が楽な方でやる。

079【妄想日記④】(2024/7/17)

ある高速道路のサービスエリアの出来事である。喉が渇いたので自動販売機で麦茶でもと思い、駐車場に止め自動販売機が並んでいるエリアまで行った。自動販売機のある一角への入り口にある看板を見て絶望した。

「新紙幣に対応していません」と赤く書かれていた。

財布の中にはATMからおろしたての新紙幣しかなかったからだ。

20台ある自動販売機はどれも新紙幣に対応していなかった。

仕方がないので両替をしてもらおうとサービスエリアの売店に行ことしたら、売店に入ったところに、「紙幣交換機」が置いてあった。

新紙幣を旧紙幣に交換する機械が置いてあったのだ。

そこで、千円札を交換して自動販売機に行き目的の麦茶を購入した。

駐車場に帰るとき、看板を良く見ると、「新紙幣は売店の機械で交換できます」と少し小さく書かれていた。

この事があってから、財布には新旧の紙幣を入れておくようになった。

(2024/7/17)

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

【2018年】

P=n^3-7n+9が素数となる整数nをすべて求めよ。

a≡0, b≡1, c≡-1 (mod 3)のとき

p=a+b+c→p≡0

q=ab+bc+ca→q≡-1

r=abc→r≡0

とする。

a,b,cは、x^3-px^2+qx-r=0の解

P=n^3-pn^2+qn-r+3が素数となる整数n

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

p=3s, q=3t-1, r=3uとおける。

P=n^3-3sn^2+(3t-1)n-3u+3

=n^3-n-3sn^2+3tn-3u+3

=(n^3-n)-3(sn^2-tn+u-1)

=n(n+1)(n-1)-3(sn^2-tn+u-1)

n(n+1)(n-1)は3の倍数だから、

Pは3の倍数

Pは素数だから、P=3

P=n^3-pn^2+qn-r+3=3

n^3-pn^2+qn-r=0だから、

n=a,b,c

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

a≡0, b≡1, c≡-1 (mod 3)のとき、

P=(n-a)(n-b)(n-c)は3の倍数

P+3が素数となる整数nは、

a,b,cである。

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

【例】a=-3, b=1, c=2

(n+3)(n-1)(n-2)=n^3-7n+6

P=n^3-7n+9が素数となる整数nは、

-3,1,2→【2018 入試問題】

P=n^3+sn^2+tn+u

s≡u≡0 (mod 3)

t≡-1 (mod 3)

のとき、Pは3の倍数

【例】a=3, b=-2, c=2

p=3, q=-6-4+6=-4, r=-12

P=n^3-3n^2-4n+15が素数となる整数n

【解】

P=n^3-n-3n^2-3n+15

=n(n+1)(n-1)-3(n^2-n+5)

n(n+1)(n-1)は3の倍数だから、

Pも3の倍数

Pは素数だから、P=3

n^3-3n^2-4n+15=3

n^3-3n^2-4n+12=0

n^2(n-3)-4(n-3)=0

(n-3)(n^2-4)=0

(n-3)(n+2)(n-2)=0

よって、n=3,-2,2

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

a≡0, b≡1, c≡-1, d≡2, e≡-2 (mod 5)

P=(n-a)(n-b)(n-c)(n-d)(n-e)は5の倍数

P+5が素数となる整数nは、

a,b,c,d,eである。

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

P=n^5+pn^4+qn^3+rn^2+sn+t

p≡q≡r≡t≡0 (mod 5)

s≡4≡-1 (mod 5)

とき、Pは5の倍数

(2024/6/30)