Number Theory Assignment #4 Solutions - Foundations of Mathematics

This document presents a comprehensive solution set for a number theory assignment. The solutions cover a range of topics, including the computation of least residues using Fermat's Little Theorem and modular arithmetic, proving divisibility properties, and demonstrating the application of mathematical induction. The assignment explores the properties of prime numbers, including proofs related to quadratic residues and Fermat's Little Theorem, and investigates the implications when the prime number condition is not met. Furthermore, the solutions include the use of the contrapositive of Fermat's Little Theorem to prove the compositeness of a number and explores pseudoprimes. The assignment also delves into Euler's theorem and its application, as well as proofs using induction, and concludes with a discussion on divisors.

1
Theory of numbers
Name:
Date:

2
Question 1
a)
Least residue of 3237 (mod 13)Solution
From Fermat’s little theorem;
Ap-1 ≡ 1 (mod p), suppose p is a prime number, a is an integer and non-multiple of p
Since 13 is an integer;
3237 (mod 13) = 313−1 ≡ 1 (mod 13)
319 ×12+ 9 = (312 )19 ×39
Therefore,
3237 ≡(312)19 ×39 ≡ 119 × 39 ≡ 9(mod 13)
b)
29194 (mod 56)Solution
Using congruence
291 ≡29(mod56)
292 ≡37 ( mod 56 )
294 ≡ 66(mod 56)
298 ≡68 (mod 56)
2916 ≡7( mod 56)
2932 ≡ 66( mod56)
2964 ≡18( mod 56)
29128 ≡ 42(mod 56)
The exponent, 194 can be written as 194 = 128 + 64 + 2
Therefore, 29194 = 29128 × 2964 × 292 ≡ 13(mod 56)
Question 2

3
Proof that 5460 | n25 − n.Solution
We use mathematical induction to prove this
Since 0 is the first integer which is not negative, the basic step is n=0
i) If n=0, then 5460 | 025 – 0 0r 5460|0 which is true.
ii) Suppose s ≥ 0 we have to prove that 5460|(s25 – s)
Therefore, 5460|((s+1)25 – (s+1))
If 5460|(s25-s) then s25 – s = 25k for k ∈ Z
We observe that,
(s+1)25 – (s+1) = (s+1)5 (s+1)5 (s+1)5 (s+1)5(s+1)5
But (s+1)5 = s5 + 5s4 + 10s3 + 10s2 + 5s +1
(s+1)25 = (s5 + 5s4 + 10s3 + 10s2 + 5s +1)5
(s+1)25 – (s+1) = (s5 + 5s4 + 10s3 + 10s2 + 5s +1)5 – s - 1
= {5 (k + s4 +2 s3 +2 s2 +s ) }5
−s−1
This indicates that, ((s+1)25 – (s+1)) is a multiple of 5 and therefore 5460|((s+1)25 – (s+1)) which implies
that
5460 | n25 – n
Question 3
a)
From a p−1 ≡1 mod ( p )
(a p−1)2 ≡ 1 mod ( p )
p∨ ( ap−1 )2
−1=p∨(ap−1 +1)a p−1−1¿
Since p is prime then, p∨(a p−1+1) and p∨ap−1−1 ¿
That is, a p−1 ≡1(mode p) and a p−1 ≡−1(mod p)
From which a p−1 ≡± 1(mod p)
b)
If p is not prime, then;

4
a p−1 ≢1 (modp)
Therefore p ∤( ap−1 +1) and p ∤ap −1 −1¿
That is a p−1 ≢1 (mod p) and a p−1 ≢−1( mod p)
And thus a p−1 ≢ ±1(mod p)
c)
From a p−1 ≡1 mod ( p )
(a
p−1
2 )2 ≡ 1mod ( p )
p∨ ( a
p−1
2 )
2
−1= p∨( a
p−1
2 +1)(a
p−1
2 −1)
Since p is prime then, p∨(a
p −1
2 +1) and p∨a
p−1
2 −1 ¿
That is, a
p−1
2 ≡1(mode p) and a
p−1
2 ≡−1(mod p)
From which a
p−1
2 ≡± 1(mod p)
Question 4Solution
The contrapositive of Little theorem is: a p−1 ≢1 (modp)
Suppose we assume that 30030 is prime and we choose a base = 7 = a
Therefore, 730030 −1 =730029 ≡147 ( mod 30030 ) hence according to Fermat’s Little theorem, 30030 is not
prime.
Question 5Solution
Let x=2p −1
Since p is prime, 2p=2modp∧ p∨2p−2
Therefore 2p−2=kp for someinteger k
Thus, 2m−1=22 p−2=2kp

5
We have, x=2p −1∨2kp −1 =2x−1
Thus 2x−1 ≡1(mod x )
Therefore we conclude that x=2p −1 is a pseudoprime to the base 2
Question 6Solution
From Euler’s theorem:
If n ≥ 1 and the gcd (a, n) = 1, then a∅(n) ≡1(mod n)
Now, from the above theorem;
a∅(b) ≡ 1 (mod b)
b∅(a) ≡ 1 (mod a)
Furthermore;
a∅(b) ≡0(mod a) since a|a∅(b)
b∅(a) ≡0 (mod b) since b|b∅(a)
Therefore,
a∅(b) + b∅(a) ≡ 1 (mod b)…………………………………… (i)
a∅(b) + b∅(a) ≡ 1 (mod a)……………………………………. (ii)
From equation (i) we have;
a∅(b) + b∅(a) ≡ 1 (mod ab) ; (gcd (a, b) =1)
Question 7
a)Solution
For any integer k ∈ {1,2,3,…,p-1} , ( p
k ) ≡ 0(mod p)
( p
k )= p !
( p−k ) ! k !
( p
k )= p ( p−1 ) !
( p−k ) ! k !
Let x = (p – 1)! , y = (p – k)!k!

6
y. ( p
k )= p . x
p|y.( p
k )
However, p∤y since y is a product of integers all less than p. Therefore, p does not divide the product.
P| ( p
k ) since p is prime and thus if p|xy and p ∤x then p|y
b)Solution
(a + b)p ≡ ap + bp (mod p)
From binomial theorem, (a+b)p=∑
k=0
p
( p
k ) ak bp−k
Furthermore,∑
k=0
p
( p
k )ak bp−k =ap +∑
k=1
p−1
(p
k )ak b p−k +b, 1≤ k ≤ p−1
( p
k ) ≡ 0 (mod p)
Thus, ( p
k ) ak bp−k ≡0 (mod p) and ∑
k=1
p−1
( p
k )ak b p−k ≡ 0(mod p)
Therefore,
∑
k=0
p
( p
k ) ak bp−k =ap +b p
c)Solution
Using induction,
For a = 1, 1p ≡1 (mod p)
From a p−1 ≡1(mod p) we multiply both through by a to obtain:
a × ap−1 ≡ a( mod p)
Therefore, a1+ p−1 ≡ a( mod p)
Which simplifies to: a p ≡ a(mod p)

7
Question 8
a)Solution
Assuming that n is an integer greater than zero and d is a positive divisor
The set of positive integers includes:
{0,1,2,3,…,m}
We have n|d
Since n can be any positive integer, it follows that:
a=∑
n=0
m n
d
b)Solution
Suppose we have a set defined as follows, [n] = {1, 2, 3,…,n} of size n
We define an equivalence relation as below:
m m' ↔ ( m, n ) = ( m' , n )
m = {0<m’ ≤ n : (m’,n) = d}
Where d = (m,n)|n which is made up of all positive elements
m’ ≤ n and (m’,n) = d
Therefore, m'
d ≤ n
d such that ( m'
d , n
d )=1
The total sum of this is ϕ ( n
d ) elements
Since there is a ‘single class for each positive divisor of n we have;
n=∑
d∨n
ϕ n
d
Since d handles all divisors of n, n
d does so too
Therefore, n=n=∑
d∨n
ϕ ( d)

8
References
Dedekind, R. (2012). Essays on the Theory of Numbers. Courier Corporation.
Koshy, T. (2002). Elementary Number Theory with Applications. Cambridge, MA: Academic
Press.
LeVeque, W. J. (2014). Elementary Theory of Numbers. North Chelmsford, MA: Courier
Corporation.