ผลต่างระหว่างรุ่นของ "01204211/homework6 number theory 1"
Jittat (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย ': ''This is part of 01204211-58'' '''Due:''' TBA '''H.1'''') |
Jittat (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 11 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 1: | แถว 1: | ||
: ''This is part of [[01204211-58]]'' | : ''This is part of [[01204211-58]]'' | ||
| − | '''Due:''' | + | '''Due:''' 21 Oct, 2015 |
| − | '''H.1''' | + | '''H.1''' (LPV-6.1.3) Prove that if <math>a|b</math> and <math>a|c</math>, then <math>a|b+c</math> and <math>a|b-c</math>. |
| + | |||
| + | |||
| + | '''H.2''' (LPV-6.10.3) Prove that if <math>c\neq 0</math> and <math>ac|bc</math>, then <math>a|b</math>. | ||
| + | |||
| + | |||
| + | '''H.3''' Prove that for integers <math>a</math> and <math>b</math> and positive integer <math>q</math> the following statements are true. | ||
| + | |||
| + | (a) <math>(a+b)\;\bmod\; q = ((a\;\bmod\; q) + (b\;\bmod\; q))\;\bmod\; q</math> | ||
| + | |||
| + | (b) <math>(ab)\;\bmod\; q = ((a\;\bmod\; q) \times (b\;\bmod\; q))\;\bmod\; q</math> | ||
| + | |||
| + | Notes: this fact may be useful: If <math>r=a\;\bmod\;q</math>, then there exists an integer <math>k</math> such that <math>a=kq+r</math>. | ||
| + | |||
| + | |||
| + | '''H.4''' (LPV-6.1.6) (a) Prove that for every integer <math>a</math>, <math>a-1|a^2-1</math>. | ||
| + | |||
| + | (b) More generally, prove that for every integer <math>a</math> and positive integer <math>n</math>, <math>a-1|a^n-1</math>. | ||
| + | |||
| + | |||
| + | '''H.5''' (LPV-6.3.3) Suppose that <math>a</math> and <math>b</math> are integers and <math>a|b</math>. Suppose that <math>p</math> is a prime and <math>p|b</math>, but <math>p\not| a</math>. Prove that <math>p|(b/a)</math>. | ||
| + | |||
| + | |||
| + | '''H.6''' Let <math>p</math> be a prime. Consider integers <math>a</math> and <math>b</math>, such that <math>1\leq a,b\leq p-1</math>. Prove that if <math>a \ \bmod p = b \ \bmod p</math> then <math>a=b</math>. | ||
| + | |||
| + | |||
| + | '''H.7''' (LPV-6.10.7) Prove that if <math>a > 3</math>, then <math>a</math>, <math>a+2</math>, and <math>a+4</math> cannot be all primes. (Can they all be powers of primes?) | ||
| + | |||
| + | |||
| + | '''H.8''' (LPV-6.10.14) Find pairs of integers for which the Euclidean Algorithm runs for (a) 2 steps, and (b) 6 steps. | ||
| + | |||
| + | ''Notes:'' ''Recall that the Euclidean algorithm <tt>GCD(a,b)</tt> is defined as:'' | ||
| + | |||
| + | FUNCTION GCD(a,b) | ||
| + | 1. if b|a then return b endif | ||
| + | 2. return GCD(b, a mod b) | ||
| + | |||
| + | ''In this problem let's count the number of steps the algorithm runs by the number of times function GCD is called. For example, GCD(8,2) runs 1 one step, but GCD(18,10) runs for 3 steps. In this problem, you only have to give '''examples''' of pairs for cases (a) and (b).'' | ||
| + | |||
| + | |||
| + | '''H.9''' (LPV-6.10.16) Prove that for every positive integer <math>m</math>, there is a Fibonacci number, beside <math>F_0=0</math>, divisible by <math>m</math>. For example, when <math>m=4</math>, we have <math>F_6=8</math> which is divisible by <math>m</math>. | ||
รุ่นแก้ไขปัจจุบันเมื่อ 16:09, 11 ตุลาคม 2558
- This is part of 01204211-58
Due: 21 Oct, 2015
H.1 (LPV-6.1.3) Prove that if and , then and .
H.2 (LPV-6.10.3) Prove that if and , then .
H.3 Prove that for integers and and positive integer the following statements are true.
(a)
(b)
Notes: this fact may be useful: If , then there exists an integer such that .
H.4 (LPV-6.1.6) (a) Prove that for every integer , .
(b) More generally, prove that for every integer and positive integer , .
H.5 (LPV-6.3.3) Suppose that and are integers and . Suppose that is a prime and , but . Prove that .
H.6 Let be a prime. Consider integers and , such that . Prove that if then .
H.7 (LPV-6.10.7) Prove that if , then , , and cannot be all primes. (Can they all be powers of primes?)
H.8 (LPV-6.10.14) Find pairs of integers for which the Euclidean Algorithm runs for (a) 2 steps, and (b) 6 steps.
Notes: Recall that the Euclidean algorithm GCD(a,b) is defined as:
FUNCTION GCD(a,b) 1. if b|a then return b endif 2. return GCD(b, a mod b)
In this problem let's count the number of steps the algorithm runs by the number of times function GCD is called. For example, GCD(8,2) runs 1 one step, but GCD(18,10) runs for 3 steps. In this problem, you only have to give examples of pairs for cases (a) and (b).
H.9 (LPV-6.10.16) Prove that for every positive integer , there is a Fibonacci number, beside , divisible by . For example, when , we have which is divisible by .
