Math 255 Lab:
Elementary Number Theory

March 27, 2009

John Voight

1.  Find the greatest common divisor of 9876543210 and 123456789.

GCD[9876543210,123456789]

2.  Find the least common multiple of 4382136 and 14400.

3.  Find the least positive residue modulo 10403 of (7651^(20!))

Mod[7651^Factorial[20],10403]

PowerMod[7651,Factorial[20],10403]

4.  Compute integers a and b such that 13409823x + 23742372y = 3.

a = 13409823;
b = 23742372;
ExtendedGCD[a,b]

5.  What is the inverse of 734342 modulo 1533331?

6.  Solve the simultaneous system of congruences: 
  x ≡ 1 (mod 12341234567), 
  x ≡ 2 (mod 750000057),
  x ≡ 3 (mod 1099511627776).
Verify that your answer is correct.

7.  When is the number 4^n + n^4 divisible by 5?

Table[4^n+n^4,{n,20}]

8.  Find the 200th Fibonacci number.

Fibonacci[200]

9.  When is the nth Fibonnaci number divisible by 7?  By 11?

10.  Find the 1000000th prime.

Prime[1000000]

11.  Plot the nth prime as a function of n for 1 ≤ n ≤ 100.

ListPlot[Table[Prime[n],{n,100}]]

12.  Plot the nth Fibonacci number as a function of n for 1 ≤ n ≤ 100.  How quickly do these numbers grow?  About how many digits does the nth Fibonnaci number have?

13.  About how many digits does the (10^n) th prime have?

14.  Find the smallest prime greater than 100000000.

NextPrime[100000000]

PrimeQ[100000000]

n = 100000000;
While[!PrimeQ[n],n++];
n

15.  Find the smallest pair of twin primes greater than 100000000.

16.  Factor the integer 111111111111111111.

FactorInteger[111111111111111111]

17.  Compute the sum of divisors of 3859201872.

DivisorSigma[1,3859201872]

18.  Compute the sum of the 3rd powers of the divisors of 3859201872

19.  A Wilson prime is a prime p for which (p-1)! ≡ -1 (mod (p^2)).  Find all Wilson primes less than 10000.

primes := Table[Prime[n],{n,20}]
primes

Table[{p,Mod[Factorial[p-1]+1,p^2]},{p,primes}]

20.  Find the smallest prime factor of (Subscript[p, 1])(Subscript[p, 2])... (Subscript[p, k])+1 where (Subscript[p, 1]), (Subscript[p, 2]), ..., (Subscript[p, k]) are the kth smallest primes for all positive integers k not exceeding 20.

21.  What is the largest value of n such that n! has fewer than 100 decimal digits?

22.  Can you find a positive integer n ≠ 5186 such that ϕ(n) = ϕ(n+1) = ϕ(n+2)?  Can you find  consecutive positive integers n, n + 1, n + 2, n + 3 such that ϕ(n) = ϕ(n+1) = ϕ(n+2) = ϕ(n+3)?

23.  Encrypt the message BEST WISHES using RSA.

ConvertString[str_String] := 
Fold[Plus[27#1, #2]&, 0, ToCharacterCode[str]-64]
p = NextPrime[Pi 10^10];
q = NextPrime[10^10];
n = p*q;
ConvertNumber[num_Integer] := 
FromCharacterCode[IntegerDigits[%160,27]+64]

ConvertString["ABCDEFG"]

IntegerDigits[%125,27]

a = ConvertString["BESTWISHES"]

e = 257;
b = PowerMod[a,e,n]

d = PowerMod[257,-1, (p-1)(q-1)]

PowerMod[b,d,n]

FromCharacterCode[IntegerDigits[%160,27]+64]

24.  Find all solutions of x^4 - 13x^3 + 11x - 3 ≡ 0 (mod (7^8)).