information to use:

def isPrime(n): for i in range(2, n): if n % i == 0: return False return True def listPrimes(n): typelist = [] i = 2 while i <= n: if isPrime(i): typelist.append(i) i += 1 return typelist def nPrimes(n): typelist = [] i = 2 while len(typelist) < n: if isPrime(i): typelist.append(i) i += 1 return typelist print(listPrimes(100)) print(nPrimes(100))

THE QUESTION TO ANSWER:

Prime numbers satisfy another property. If one has three integers m,n and k, we say m and n are congruent modulo k if the remainder from dividing m by k is the same as the remainder from dividing n by k. We can then write m n( mod k). For instance, the numbers 19 and 47 are congruent modulo 7 since 19 = 27+5 and 47 = 67+5. The remainder from division of both 19 and 47 by 7 is 5. The congruence relation is preserved by arithmetic operations. If m1 n1( modk)andm2 n2( modk),thenm1+m2 n1+n2( modk)andm1m2 n1n2( mod k). Prime numbers and congruences are related. There is a theorem that states: If p is a prime number, then ap a( modp) (1) for any integer p > a > 0. For instance, for p = 3, we observe 13 = 11( mod3) (2) 23 = 82( mod3) (3) 33 = 273( mod3) (4) 43 = 644( mod3) (5) (6) Therefore, p = 3 satisfies ap a( mod p). Here, we have tried out a = 1, 2, 3, 4 although 4 is not guaranteed to work. This relation does not in general hold true for composite numbers.

1. Write a function listPrimeLike(n) which accepts n as an input and returns the list of prime-like numbers less than n using the congruence relation check.

2. Write a function nPrimeLike(n) which accepts n as an input and re- turns the first n number of prime-like numbers using the congruence rela- tion check.

3. Compare the list of the first 200 primes from your nPrimes function and compare them with the output from your nPrimeLike function. What conclusions can you draw? Your comparison must be quantitative and also avoid large output text. Use list comprehensions or write your own code to filter out elements which may be different in the two lists. If you dont see any difference push harder to n = 500.(Look up Carmichael numbers) Tip: To calculate the remainder of the division of an with k, use (a**n) %k. For speed, you can also use pow(a,n,k) which does the same. The function pow(a,n) just returns an.

PLEASE USE PYTHON, THANKS IN ADVANCE.