Selected Answers to Problem Set 11

1. We can look at the first few factors of 2n mod 11: 
21 mod 11 = 2		27 mod 11 = 7
22 mod 11 = 4		28 mod 11 = 3
23 mod 11 = 8		29 mod 11 = 6
24 mod 11 = 5		210 mod 11 = 1
25 mod 11 = 10		211 mod 11 = 2
26 mod 11 = 9		212 mod 11 = 4
That is, at n = 11, the process repeats (after all, this function is modular) so n can be expressed as 10a + b, where a,b are integers. So 212345 mod 11 = 210*1234 + 5 mod 11 = 25 mod 11 = 10. You can create a Maple function such as:

f:=(x) -> 2^x mod 11;

which will let you simply enter f(12345) to get back 10.
2. An integers n is not prime if and only if there exists two integers a,b such that a and b do not equal 1 or n and a*b = n. We show that either a <= sqrt(n) or b <= sqrt(n); we can simply show the first case and switch a with b to show the second. Suppose both a and b were greater than sqrt(n); then a*b would be greater than n, which contradicts our claim that a*b = n. Therefore, if n is not prime, then a*b=n implies that either a <= sqrt(n) or b <= sqrt(n).
3. The number 36,287 is not prime; it has divisors (1,131,277,36287). For this problem and the next you may have wanted to write a Perl script: mine can be found here.
4. The primes numbers between 1 and 300 are (2, 3, 4, 5, 7, 9, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 289, 293). These were found by using the listprimes.pl script found in the primes directory from the link above.
5. Let 3k+1 be prime for some integer k. Because 3k+1 is prime, 3k+1 must be odd, which entails that 3k is even. Then there exists k2such that 6k2 = 3k; we simply let k2 = k / 2. Then 6k2 + 1 is also prime.
6. For part (a), know that any integer can be expressed as 3k, 3k+1, or 3k+2 for some k. Let a positive integer n = 3k+2. If n is even then it has a prime factor of the form 3k+2, where k = 0. If n is odd and prime, then it has n as a prime factor. The most interesting case is when n is odd and composite. Then it has two odd factors (since n is odd). Also, since n = 3k+2, n is not divisible by 3. Therefore, the two factors are of the form 3a+1 and 3a+2. 
(3a+1)(3b+1) = 9ab + 3a + 3b + 1 = 3(3ab + a + b) + 1
(3a+1)(3b+2) = 9ab + 6a + 3b + 2 = 3(3ab + 2a + b) + 2
(3a+2)(3b+2) = 9ab + 6a + 6b + 4 = 3(3ab + 2a + 2b) + 4
The only combination to yield a answer of the form 3k+2 is (3a+1)(3b+2), where k = 3ab + 2a + b. Therefore, one of the factors is of the form 3b+2; this factor is checked through this same process until a factor of it is prime.

For n = 4k + 3 we know that n is odd, so it is the product of two odd numbers of the form 4a+1 and 4a+3. 

(4a+1)(4b+1) = (16ab + 4a + 4b + 1)   = 4(4ab + a + b) + 1
(4a+1)(4b+3) = (16ab + 12a + 4b + 3)  = 4(4ab + 3a + b) + 3
(4a+3)(4b+3) = (16ab + 12a + 12b + 9) = 4(4ab + 3a + 3b) + 9
Again, the only combination to have the form 4k+3 is (4a+1)(4b+3) which means that 4b+3 is either prime or it also has a prime factor (which means 4k+3 has the same prime factor).

Finally, for n = 6k + 5 we know that n is odd, so it is the product of two odd factors. Also, n is not divislbe by three, so its factors have two possible forms: 6k+1 and 6k+5: 

(6a+1)(6b+1) = (36ab + 6a + 6b + 1)    = 6(6ab + a + b) + 1
(6a+1)(6b+5) = (36ab + 30a + 6b + 5)   = 6(6ab + 5a + b) + 5
(6a+5)(6b+5) = (36ab + 30a + 30b + 25) = 6(6ab + 5a + 5b) + 25
Again, the only combination of the form 6k + 5 is (6a+1)(6b+5); 6b+5 is either prime or has a prime factor of this form (which implies 6k+5 has this factor as well).
7. Let (p0, ..., pn) be a list of primes of the form 4k+3, and let p = p0 * ... * pn.
8. The idea is to use some function to calculate the greatest common factor of two numbers. The simplest way is to notice that the greatest common factor of two numbers is the same as the gcf of either number and the difference of the two numbers (i.e. gcf(15,6) = gcf(15,9) = gcf(6,9)). Euler's method takes it one step further and decreases the number of steps needed: gcf(x,y) = gcf(y,x%y), and gcf(x,0) = x.

See my script here, which utilizes Euler's formula for calculating the greatest common factor of two numbers. This program uses a subroutine, which shouldn't be that difficult to understand.

Were these answers helpful?
Yes
No
 Name (optional):