Theory of Numbers

1
Theory of numbers
Name:
Date:
Question 1

2
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( mod 56)
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
Proof that 5460 | n25 − n.Solution

3
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;
a p−1 ≢1 (modp)
Therefore p ∤(ap−1 +1) and p ∤ap −1 −1¿