แบบฝึกหัด สอวน.ทฤษฎีจำนวน เรื่อง การหารลงตัว

[<KAB555>]

แบบฝึกหัดเรื่องทฤษฎีจำนวน

1) จงแสดงว่า $(3n+4,2n+3)=1$ สำหรับทุกๆ จำนวนเต็ม $n$
2) จงแสดงว่า ผลคูณของจำนวนเต็ม $n$ ที่เรียงต่อเนื่องกันจะหารด้วย $n!$ ลงตัว
3) จงหาจำนวนเต็มบวก $n$ ทั้งหมดที่ทำให้ $2^{n-1}$ หาร $n!$ ลงตัว
4) ให้ $n$ เป็นจำนวนเต็มบวก จงแสดงว่า $10^n+18n-1$ หารด้วย $27$ ลงตัว
5) จงตรวจสอบว่า "$n$ หารผลบวกของจำนวนเต็มบวก $n$ จำนวนที่เรียงต่อเนื่องลงตัวเสมอ" จริงหรือไม่ พร้อมทั้งให้เหตุผล
6) จงหาจำนวนเซตที่สร้างจากจำนวนเต็มบวกอย่างน้อย $2$ จำนวนที่ผลรวมของสมาชิกในเซตเท่ากับ $100$
7) จงแสดงว่า ถ้า $a$ และ $b$ เป็นจำนวนเต็มบวกแล้ว $(2^a-1,2^b-1)=2^{(a,b)}-1$
8) จงแสดงว่า $n^5-5n^3+4$ หารด้วย $120$ ลงตัว สำหรับทุกๆ จำนวนเต็มบวก $n$
9) มีจำนวนนับตั้งแต่ $1$ ถึง $100$ รวมทั้งสิ้นกี่จำนวนซึ่งเมื่อหารด้วย $6$ แล้วเหลือเศษ $2$ และเมื่อหารด้วย $14$ เหลือเศษ $1$
10) จงหาจำนวนของจำนวนเต็มบวกที่หาร $(30)^4$ ลงตัว
11) จำนวนเต็มบวก $n$ ที่มากที่สุดที่ทำให้ $10^n$ หาร $1005!$ ลงตัว มีค่าเท่าใด
12) จงหาจำนวนของจำนวนเต็มตั้งแต่ $1$ ถึง $100$ ที่หารด้วย $2,3,4,5$ ลงตัว
13) ให้ $n$ เป็นจำนวนเต็ม จงแสดงว่า $n^5-n$ หารด้วย $30$ ลงตัว
14) มีจำนวนเต็มทั้งหมดกี่จำนวนที่อยู่ระหว่าง $1$ ถึง $2545$ ที่ $3$ หรือ $7$ หารลงตัว
15) จงหาจำนวนเต็มบวก $x,y,z$ ทั้งหมดที่ $x<y<z$ และ $(x,y)=(x,z)=(y,z)=1$ รวมทั้ง $z$ หาร $x+y$
16) จงแสดงว่า ถ้า $n\in \mathbb{N} $ แล้ว $[n,n+2]=\frac{1}{2}n(n+2) $
17) จงแสดงว่า ถ้า $n\in \mathbb{Z} $ แล้ว $4\nmid (n^2+1)$
18) จงแสดงว่า ถ้า $(a,4)=2$ และ $(b,4)=2$ แล้ว $(a+b,4)=2$
19) ให้ $a,b,c\in \mathbb{Z} $ จงพิสูจน์ว่า $6|(a+b+c)$ ก็ต่อเมื่อ $6|(a^3+b^3+c^3)$
20) $n,k\in \mathbb{N} $ โดยที่ $n\geqslant 2$ จงพิสูจน์ว่า $(n-1)^2|(n^k-1)$ ก็ต่อเมื่อ $(n-1)|k$
21) จงพิจารณาว่าข้อความต่อไปนี้เป็นจริงหรือเท็จ ถ้าข้อความนั้นเป็นจริงจงพิสูจน์ แต่ถ้าข้อความนั้นเป็นเท็จจงยกตัวอย่างค้าน
(21.1) ถ้า $(a,b)=1$ แล้ว $(2a+b,a+2b)=1 หรือ 3$
(21.2) ถ้า $(a,b)=1$ แล้ว $(a+b,a^2+b^2)=1 หรือ 2$
(21.3) ถ้า $(a,b)=1$ แล้ว $(a+b,a^2-ab+b^2)=1 หรือ 3$
22) จงแสดงว่า ถ้า $(3!)^n|(3n)!$ สำหรับทุกจำนวนเต็ม $n$ ที่ $n\geqslant 0$

[<KAB555>]

1) จงแสดงว่า $(3n+4,2n+3)=1$ สำหรับทุกๆ จำนวนเต็ม $n$

$3n+4=(2n+3)(1)+(n+1)$
$2n+3=(n+1)(2)+1$
$n+1=1(n+1)$
ดังนั้น $(3n+4,2n+3)=1$

4) ให้ $n$ เป็นจำนวนเต็มบวก จงแสดงว่า $10^n+18n-1$ หารด้วย $27$ ลงตัว

ให้ $n\in \mathbb{N} $ และ $P(n):27|10^n+18n-1$
1) พิจารณา $n=1$ $P(1)$ เป็นจริง เพราะว่า $27|10^1-18(1)-1$
2) ให้ $k\in \mathbb{N} $ ที่ $k>1$ และ $P(k)$ เป็นจริง นั่นคือ $27|10^k+18k-1$ ทำให้ $27|10(10^k+18k-1)$ [จะแสดงว่า P(k+1) เป็นจริง]
พิจารณา $10(10^k+18k-1)=10^{k+1}+180k-10=10^{k+1}+18k+18-1+162k-27=(10^{k+1}+18(k+1)-1)+162k-27$
เนื่องจาก $162k-27 =27(6k-1)$ หารด้วย 27 ลงตัว ดังนั้น $27|10^{k+1}+18(k+1)-1$
P(k+1) เป็นจริง

7) จงแสดงว่า ถ้า $a$ และ $b$ เป็นจำนวนเต็มบวกแล้ว $(2^a-1,2^b-1)=2^{(a,b)}-1$

ให้ $(a,b)=d$ จะได้ $a=dp$ และ $b=dq$ สำหรับบาง $p,q\in \mathbb{Z} $
จะได้ $2^a-1=(2^d)^p-1$ และ จะได้ $2^b-1=(2^d)^q-1$ $\therefore 2^d-1|2^a-1$ และ $2^d-1|2^b-1$ จะได้ $2^d-1|(2^a-1,2^b-1)$
ให้ $(2^a-1,2^b-1)=D$ จะได้ $2^a-1\equiv 0 $(mod D) และ $2^b-1\equiv 0 $(mod D) $\Rightarrow 2^a\equiv 1$ (mod D) และ $2^b\equiv 1$ (mod D)
จะได้ $(2^a)^x(2^b)^y\equiv 1$ (mod D) $\Rightarrow 2^{ax+by}\equiv 1$ (mod D) ซึ่ง x,y เป็นจำนวนเต็มที่ทำให้ $d=(a,b)=ax+by$
$\Rightarrow 2^d-1\equiv 0$ (mod D) $\Rightarrow D|2^d-1\Rightarrow (2^a-1,2^b-1)|2^d-1$
จาก $2^d-1|(2^a-1,2^b-1)\Rightarrow 2^{(a,b)}-1\leqslant (2^a-1,2^b-1)$
และ $(2^a-1,2^b-1)|2^d-1\Rightarrow 2^{(a,b)}-1\geqslant (2^a-1,2^b-1)$
จะได้ $2^{(a,b)}-1=(2^a-1,2^b-1)$

[<KAB555>]

ข้อ 3 , 6, 19 ,20 , 22 ทำยังไงหรือคะ

[nooonuii]

3) จงหาจำนวนเต็มบวก $n$ ทั้งหมดที่ทำให้ $2^{n-1}$ หาร $n!$ ลงตัว

หาว่า $n!$ มี $2$ เป็นตัวประกอบได้ทั้งหมดกี่ตัว

[nooonuii]

22) จงแสดงว่า $(3!)^n|(3n)!$ สำหรับทุกจำนวนเต็ม $n$ ที่ $n\geqslant 0$

ใช้ induction

[nooonuii]

19) ให้ $a,b,c\in \mathbb{Z} $ จงพิสูจน์ว่า $6|(a+b+c)$ ก็ต่อเมื่อ $6|(a^3+b^3+c^3)$

$(a+b+c)^3 = a^3+b^3+c^3 + 3(a+b)(b+c)(c+a)$

[<KAB555>]

ไปลองทำมาค่ะ

19) ให้ $a,b,c\in \mathbb{Z} $ จงพิสูจน์ว่า $6|(a+b+c)$ ก็ต่อเมื่อ $6|(a^3+b^3+c^3)$

$(\Rightarrow )$ จาก $6|(a+b+c)$ แสดงว่ามี $k\in \mathbb{Z} $ ที่ทำให้ $a+b+c=6k$
ถ้า $a+b+c=6k$ [จะพิสูจน์ว่า $6|(a^3+b^3+c^3)$]
จาก $(a+b+c)^3=a^3+b^3+c^3+3(a+b)(b+c)(c+a)$
จะได้ $(6k)^3=a^3+b^3+c^3+3(a+b)(b+c)(c+a)$
เนื่องจาก จำนวนเต็มสามจำนวน ต้องมีจำนวนอย่างน้อยสองจำนวนที่บวกกันแล้วหารด้วย 2 ลงตัว ดังนั้น $2|(a+b)(b+c)(c+a)$ ให้ $(a+b)(b+c)(c+a)=2t$ สำหรับบาง $t\in \mathbb{Z} $
จะได้ $(6k)^3=6(36k^3)=a^3+b^3+c^3+3(2t)=a^3+b^3+c^3+6t$
เนื่องจาก 6 หาร $6(36k^3)$ และ $6t$ ลงตัว ดังนั้น $6|a^3+b^3+c^3$

22) จงแสดงว่า ถ้า $(3!)^n|(3n)!$ สำหรับทุกจำนวนเต็ม $n$ ที่ $n\geqslant 0$

ให้ $P(n)=(3!)^n|(3n)!$
1) p(1) เป็นจริง เพราะว่า $(3!)^1|[3(1)]!$ เพราะฉะนั้น P(1) เป็นจริง
2) ให้ $k\in \mathbb{N} $ ถ้า P(k) เป็นจริง เมื่อ k>1 แล้ว P(k+1) เป็นจริง
สมมติ P(k) เป็นจริง เพราะฉะนั้น $(3!)^k|(3k)!$
จะได้ $(3!)^{k+1}|3![(3k)!]$ เนื่องจาก $3![(3k)!]|(3k)!(3k+1)(3k+2)(3k+3)$
ดังนั้น $(3!)^{k+1}|(3k+3)!$ นั่นคือ $(3!)^{k+1}|(3(k+1))!$ เพราะฉะนั้น P(k+1) เป็นจริง
จะได้ P(n) เป็นจริงทุกค่า $n\in \mathbb{N} $

[ohmohm]

13) ให้ $n$ เป็นจำนวนเต็ม จงแสดงว่า $n^5-n$ หารด้วย $30$ ลงตัว

ให้พิสูจน์ว่า $n^5\equiv n (mod 30)$

เนื่องจาก $0^5\equiv 0 (mod 2)$ และ $1^5\equiv 1 (mod 2)$ ดังนั้น $n^5\equiv n (mod 2)$
เนื่องจาก $0^5\equiv 0 (mod 3)$ และ $1^5\equiv 1 (mod 3)$ และ $2^5\equiv 32 \equiv 30+2 \equiv 2 (mod 3)$ ดังนั้น $n^5\equiv n (mod 3)$
จาก Fermat's Little Theorem ได้ $n^5\equiv n (mod 5)$

เนื่องจาก $n^5\equiv n (mod 2)$ และ $n^5\equiv n (mod 3)$ และ $n^5\equiv n (mod 5)$ จึงได้ $n^5\equiv n (mod LCM[2, 3, 5])$ หรือ $n^5\equiv n (mod 30)$

ผิดถูกโปรดชี้แนะ
คล้ายๆ ข้อ http://www.mathcenter.net/forum/showthread.php?t=15917

[ohmohm]

ข้อ 17
เนื่องจาก
$0^2 \equiv 0 (mod 4)$
$1^2 \equiv 1 (mod 4)$
$2^2 \equiv 4 \equiv 0 (mod 4)$
$3^2 \equiv 9 \equiv 4(2)+1 \equiv 1 (mod 4)$

ดังนั้น
$n^2 \equiv 0, 1 (mod 4)$
(จำนวนเต็มยกกำลังสองแล้วหารด้วย 4 ได้เศษ 0 หรือ 1) และผลที่ตามมา
$n^2 + 1 \equiv 1, 2 (mod 4)$
$n^2 + 1 \not\equiv 0 (mod 4)$
$4 \nmid (n^2 + 1) $

[ohmohm]

11) จำนวนเต็มบวก $n$ ที่มากที่สุดที่ทำให้ $10^n$ หาร $1005!$ ลงตัว มีค่าเท่าใด

นั้นคือ หาว่า $1005!$ มี 0 ต่อท้ายกี่ตัว

หรือก็คือหาว่า $1005\times 1004\times 1003 \times .. \times 1000 \times .. \times 990 \times .. \times 980 \times .. \times 900 \times .. \times 800 \times .. \times 100 \times .. \times 3 \times 2 \times 1$
แต่ละตัวที่มาคูณกันนั้น มี 0 กี่ตัวบ้าง แล้วมารวมกัน

ลงท้ายด้วย 0 จำนวน 3 ตัว มี 1000 ตัวเดียว รวมจำนวน 0 ได้ 3 ตัว
ลงท้ายด้วย 0 จำนวน 2 ตัว มี 100, 200, 300, โโ‚ฌฆ 900 รวม 9 ตัว รวมจำนวน 0 ได้ 18 ตัว
ลงท้ายด้วย 0 ตัวเดียว เอาจำนวนที่ลงท้ายด้วย 0 อย่างน้อย 1 ตัว ลบออกด้วย จำนวนที่ลงท้ายด้วย 0 มากกว่า 1 ตัว นั้นคือ 10, 20,โโ‚ฌฆ,100, 110,โโ‚ฌฆ, 990, 1000 ได้ 100 ตัว เอามาลบ (9+1) ได้ 90 ตัว

รวมทั้งหมด ได้ n = 90+18+3 = 111
พลาดครับ ต้องหาว่า ถูกหารด้วย $2^k5^m$ มากสุด เท่าไหร่ (5! ก็ลงท้ายด้วย 0 แล้วครับ)


ตัวเลขตั้งแต่ 1 ถึง 1005 ถูกหารด้วย $5$ ลงตัว มีจำนวน = floor(1005/5) = 201 ตัว มีจำนวนเลข 5 รวม 201 ตัว

ตัวเลขตั้งแต่ 1 ถึง 1005 ถูกหารด้วย $5^2$ ลงตัว มีจำนวน = floor(1005/25) = 40 ตัว แต่จำนวนเลข 5 ถูกหารไปในรอบ 1005/5 แล้ว จึงเหลือ 5 อยู่ 40 ตัว

ตัวเลขตั้งแต่ 1 ถึง 1005 ถูกหารด้วย $5^3$ ลงตัว มีจำนวน = floor(1005/125) = 8 ตัว แต่จำนวนเลข 5 ถูกหาร(ถูกใช้)ไปในรอบก่อนหน้าแล้ว ทั้ง $5$ และ $5^2$ จึงเหลือ 5 อยู่หนึ่งตัวต่อตัวเลขที่ถูกหารด้วย $5^3$ ลงตัว

ตัวเลขตั้งแต่ 1 ถึง 1005 ถูกหารด้วย $5^4$ ลงตัว มีจำนวน = floor(1005/625) = 1 ตัว แต่จำนวนเลข 5 ถูกหาร(ถูกใช้)ไปในรอบก่อนๆ หน้าแล้ว เหลือ 5 อยู่หนึ่งตัวต่อตัวเลขที่ถูกหารด้วย $5^4$ ลงตัว

ส่วน $5^5 = 3125 > 1005$ จึงหยุดการหารต่อ รวมจำนวนเลข 5 มีทั้งหมด = 201+40+8+1 = 250 ตัว

ส่วนเลขสองนั้น เป็นตัวประกอบในตัวเลขระหว่าง 1 ถึง 1005 จำนวน floor(1005/2)=502 เกินพอที่จะคูณกับ 5 แล้วได้ 10

คำตอบคือ n=250

[boompt_]

ข้อ21 ทำไงคะ

[ohmohm]

ข้อ 1

gcd(3n+4, 2n+3) ; n>0
=gcd(3n+4 - (2n+3), 2n+3) ; 3n+4 > 2n+3 
=gcd(n+1, 2n+3)
=gcd(n+1, 2n+3-n-1) ; 2n+3 > n+1
=gcd(n+1, n+2) 
=gcd(n+1, n+2-n-1) ; n+1 < n+2
=gcd(n+1, 1)
=gcd(n, 1)
=1
if n<=0
gcd(3*0+4, 2*0+3)=gcd(4, 3) = 1
gcd(3*(-1)+4, 2*(-1)+3)=gcd(1, 1) = 1

ข้อ 21.1

เรากำหนดให้ $gcd(2a+b, a+2b)=d; d\in \mathbb{N} $
จะได้ว่า d หาร 2a+b ลงตัว และ d หาร a+2b ลงตัว นั้นคือ จะมี $m,n \in \mathbb{N} $ ซึ่ง
$2a+b=md$
$a+2b=nd$
เมื่อเอามาบวกลบกัน จะได้ว่า
$3a=d(2m-n)$
$3b=d(2n-m)$

โจทย์กำหนดให้ $gcd(a, b)=1$ จะได้ว่า

$3gcd(a, b)=3$
$gcd(3a, 3b)=3$
$gcd(d(2m-n) , d(2n-m))=3$
$d\times gcd((2m-n) , (2n-m))=3$
นั้นคือ d หาร 3 ลงตัว และ $0<d<=3$ d จึงเป็น 1 หรือ 3