ผลต่างระหว่างรุ่นของ "01204211/homework6 number theory 1"
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 34: | แถว 34: | ||
'''H.8''' (LPV-6.10.14) Find pairs of integers for which the Euclidean Algorithm runs for (a) 2 steps, and (b) 6 steps. | '''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: | + | ''Notes:'' ''Recall that the Euclidean algorithm <tt>GCD(a,b)</tt> is defined as:'' |
FUNCTION GCD(a,b) | FUNCTION GCD(a,b) | ||
| แถว 40: | แถว 40: | ||
2. return GCD(b, a mod b) | 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 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>. | '''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 .
