WARM WELCOME TO ALL MY FRIENDS

NUMBER THEORY

BY
SURYAKANTA NANDA
K.V.5,BBSR
 SOME GREAT MATHEMATICIANS
WHO CONTRIBUTES FOR NUMBER
THEORY ARE:

.
EUCLID(300BC) 1. Proved there are infinitely
.
many primes.
2. EUCLID’S division algorithm
Let a be an integer and d a
positive integer.
Then there are unique
integers q and r, with
0  r < d, such that a = dq + r.
 • FERMATS last theorem
FERMAT
(1601-1665) an + bn = cn has no integer
.
solutions for a,b,c when
n>2
• Fermat’s little theorem

• Perfect numbers
Numbers whose factors
excluding itself add upto
itself.
EULER • CONSIDERED AS THE
(1707-1783) FOUNDER OF NUMBER
. THEORY
• PROVED VARIOUS
PROPERTIES REGARDING
PRIME NUMBERS
• MOST FAMOUS FOR
EULERS NUMBER ‘e’
• EULER’S IDENTITY eπi = -1
• Proved there are no integral
solutions to a4 + b4 = c2
LAGRANGE
(1736-1813)
.

• FOUR SQUARE THEOREM

Every number is the sum of
four squares.
DIRICHLET
(1805-1859)
.

• DIRICHLET’S PRIME
NUMBER THEOREM
All arithmetic sequences
where the initial term and
the common difference are
co-prime contain an infinite
number of primes.
 • Ramanujan’s number
RAMANUJAN(1887-1920) 1729 = 123 + 13
=103 + 93
.

it is the smallest number

expressible as the sum of
two cubes in two different
ways.
 Introduction to Number Theory

Number theory is about integers and their properties.

We will start with the basic principles of

• PRIME NUMBERS
•CO PRIME NUMBERS
•DIVISIBILITY
• NUMBER OF FACTORS
• DIVISIBILITY WITH CONSECUTIVE INTEGERS
•DIOPHANTINE EQUATIONS
• MODULAR ARITHMETIC

10
 PRIME NUMBERS
. A positive integer p greater than 1 is called prime if the
only positive factors of p are 1 and p.

. A positive integer that is greater than 1 and is not prime

is called composite.

. The fundamental theorem of arithmetic:

Every positive integer can be written uniquely as the
product of primes, where the prime factors are written in
order of increasing size.
.Mersenne prime is a prime of the form 2q - 1.
 PRIME NUMBERS
1. There are infinitely many primes.
Proof. Suppose that p1,p2 … pn are n distinct primes.
Let N = p1p2p3 ... pn + 1
We know every natural number is a product of primes.
Hence N = q1q2 … qm , with each qi prime
If q1 = pi for some i,
then pi divides N. But pi divides N-1.
which is a contradiction.
Thus the prime q1= pn+1 is not in the list p1 … pn, and
we have constructed our new prime.
 CO-PRIME NUMBERS
• two integers a and b are said to be relatively
prime, mutually prime, or co-prime if the only positive
integer that divides both of them is 1.
• the only common positive factor of the two numbers is 1.
• gcd(a,b)=1
• There exist integers x and y such that ax + by = 1
• The two integers a and b are co-prime if and only if the point
with coordinates (a, b) in a Cartesian coordinate system is
"visible" from the origin (0,0), in the sense that there is no
point with integer coordinates on the line segment between
the origin and (a, b)
 CO-PRIME NUMBERS
• K and k+1 are always co-prime for any positive
integer k.
• K-1 and k+1 are co-primes if k is even.
• K-1 and k+1 are not co-primes if k is odd.
• K-1 and k+1 will contain a factor of 2 ,if k is
odd
 Problems on co-prime numbers
1. Explain why k and k+1 are co-prime for any
positive integer k.
Answer: Suppose k had some factor q. Then k+1
must have a remainder of 1 when divided by
q, so is not divisible by q.
 DIVISIBILITY TRICKS
• Number is divisible by 2 if last number is even.
• By 3 if digits add upto multiple of 3
• By 4 if last two digits are divisible by 4
• By 5 if last digits is 0 or 5
• By 6 if number is divisible by 2 and 3
• By 7 if (double the last digit and subtract it
from the remaining digits and see if the result
is divisible by 7
 DIVISIBILITY TRICKS
• By 8 if last three digits divisible by 8
• By 9 if digits add upto multiple of 9
• By 10 if last digits is 0
• By 11 if (difference of odd positioned digits
and even positioned digits is divisible by 11)
• By 12 if number is divisible by 3 and 4
 DIVISIBILITY PROBLEMS
1. Find the smallest positive integer which
consists only of 0s and 1s,and which is
divisible by 12.
Ans. A number divisible by 12 must be divisible
by 3 and 4. If divisible by 4, the last two digits
are divisible by 4, so last two digits must be 0.
If divisible by three, the number of 1s must
be a multiple of 3. For the smallest number,
we have exactly 3 ones.
 DIVISIBILITY PROBLEMS
[Link] 484 is multiplied by a certain number
we get the result [Link] a?
3. Every digit of a given positive integer is either
3 or 4 with each occurring at least once. The
integer is divisible by both 3 and 4. What is the
smallest such integer?
4. The eight-digit number “ppppqqqq”, where p
and q are digits, is a multiple of 45. What are
the possible values of p?
 DIVISIBILITY PROBLEMS
5. A positive integer N is written using only the
digits 2 and 3, with each appearing at least
once. If N is divisible by 2 and by 3, what is the
smallest possible integer N?
6. A positive integer M is written using only the
digits 8 and 9, with each appearing at least
once. If M is divisible by 8 and by 9, what is
the smallest possible integer M?
 DIVISIBILITY PROBLEMS
7. What is the largest six-digit palindromic number
which is exactly divisible by 15?
A palindromic number is one which reads the same
when its digits are reversed, for example 23832.
8. Find the possible values of the digits p and q,
given that the five-digit number ‘p543q’ is a
multiple of 36.
9. Find the possible values of the digits a and b,
given that the five-digit number ‘a679b’ is a
multiple of 36.
[Link] the smallest positive multiple of 35 whose
all digits are same.
 DIVISIBILITY IN EQUATIONS
[Link] interior angles of a triangle are (5x + 3y)0 ,
(3x + 20)0 and (10y + 30)0 where x , y are
positive integers. What is the value of x + y.
2. Find all positive integer solutions to
(i) 7x + 6y =90
(ii) 5x + 4y = 50
PROBLEMS ON EUCLID’S DIVISION LEMMA
[Link] numbers x and y are such that when
divided by 6, they leaves remainders 4 and 5
respectively. Find the remainder when x2 + y2 is
divided by 6.
2. A number when divided by 259 leaves a
remainder 139. What will be the remainder
when the same number is divided by 37.
3. A number being successively divided by 3,5 and
8 leaves remainders 1,4 and 7 respectively. Find
the respective remainders if the order of the
divisors be reversed.
PROBLEMS ON EUCLID’S DIVISION LEMMA

4. In dividing a number by 585, a student

employed the method of short division. He
divided the number successively by 5 ,9 and
13(factors of 585) and get the remainders 4,8
and 12 respectively. If he had divided the
number by 585 what would be the remainder.
 NUMBER OF FACTORS
• X=aqxbrxcs
• In general, we can add 1 to each of the
indices, and multiply these together to get the
number of factors.
• So above, there would be (q+1)(r+1)(s+1)
factors.
 PROBLEMS ON NUMBER OF FACTORS
1. In 2 7 x 3 2 x 5 4
(i)How many zeros does this number have on the
end?
(ii)What’s the last non-zero digit?
Answer: 2 7x 3 2 x 5 4 = 2 3 x 3 2 x (2 x 5) 4 = 2 3 x 3 2 x
10 4
Answer: Using the factors we didn’t combine to
make 2-5 pairs (i.e. factors of 10), we have 2 3 x
3 2 left. This is 72, so the last non-zero digit is 2.
PROBLEMS ON NUMBER OF FACTORS
2. How many multiples of 2013 have 2013 factors?
Ans. 2013 = 3 x 11 x 61
Firstly note that any multiple of 2013 must have at
least powers of 3, 11 and 61 in its prime
factorisation (with powers at least 1).
If there are 2013 factors, then the product of one
more than each of the powers in the prime
factorisation is 2013
We could have 3 2 x11 10 x 61 60, since (2+1)(10+1)
(60+1) = 2013
There’s 3! = 6 ways we could arrange these three
powers
 PROBLEMS ON GUSSENING ABOUT
FACTORS
1. 3n = 8k What do we know about n and k?
Answer: If the LHS is divisible by 3, then so must
the RHS. And since 8 is not divisible by 3,
then k must be. By a similar argument, n
must be divisible by 8.
 PROBLEMS ON GUSSENING ABOUT
FACTORS
2. Show that 2 n = n 3 has no integer solution for n.
Answer: Since the LHS only has prime factors of 2,
then so must the RHS. Therefore n = 2 k for
some integer k is the only possibility.
Then and equating indices, 2 k = 3k. But the RHS is
divisible by 3 while the LHS is not, leading to a
contradiction.
The given equation has no solution.
 PROBLEMS ON GUSSENING ABOUT
FACTORS
3. If 3n 2 = k(k+1), then what can we say about k and k+1?
(Recall: k and k+1 are co-prime)
Answer: If k and k+1 are co-prime, they share no factors, so the
prime factors on the LHS must be partitioned into two,
depending whether they belong to k or k+1. In n 2, each prime
factor appears twice, so they must both belong to either k or
k+1 (but can’t be in both). So far, both k and k+1 will both be
square, because each prime factor comes in twos. This just
leaves the 3, which is either a factor of k or k+1. Therefore,
one of k and k+1 is three times a square, and the other a
square.
the only valid n up to 10,000 were 2, 28, 390 and 5432.
DIVISIBILITY WITH CONSECUTIVE INTEGERS

• Every other integer is divisible by 2.

• Every third integer is divisible by 3.
• Every fourth integer is divisible by 4.
DIVISIBILITY WITH CONSECUTIVE INTEGERS

1. Which of the following is divisible by 3 for

every whole number x?
A: x 3 - x B: x C: x 3 D: x E: x 3 + x

Ans. x 3 − x = x (x 2 − 1) = (x − 1) x(x + 1),

x 3 − x is always the product of three consecutive
whole numbers when x is a whole number. As
one of these must be a multiple of 3, x 3 − x
will be divisible by 3.
DIVISIBILITY WITH CONSECUTIVE INTEGERS
2. Let n be an integer greater than 6. Prove that if n-1 and n+1
are both prime, then n 2 (n2 + 16 ) is divisible by 720.
Ans. Solution: As n-1 and n+1 are prime, n must be even ,
hence divisible by 2 (since n>6). Thus n 2 (n2 + 16 ) is
divisible by 2 4, as n 4 and 16n 2 both are.
One of n-1, n and n+1 must be divisible by 3,
but since n-1 and n+1 are prime, n must be divisible by 3.
Therefore n 2 (n2 + 16 ) must be divisible by 9.
One of n-2, n-1, n, n+1 and n+2 are divisible by 5. n-1 and n+1
can’t be as they’re prime. Therefore (n-2)n(n+2) = n 3 – 4n is
a multiple of 5. => n( n 3 – 4n)is divisible by 5 => n 4 – 4n 2 is
divisible by 5.=> n 4 + 16n 2 - 20n 2 is divisible by 5
Therefore n 2 (n2 + 16 ) is divisible by 5. Thus, n 2 (n2 + 16 ) is
divisible by 2 4 x 3 2 x 5 = 720.
 DIOPHANTINE EQUATIONS
• An equation for which we’re looking for
integer solutions.
• For example
(i)x n + y n = z n
(ii)3x + 4y = 24 Linear Diophantine Equation.
(iii) x 2 – ny 2 = 1 Pell’s Equation.
 DIOPHANTINE EQUATIONS
1. How many positive integer solutions for
(x-6)(y-10) = 15
2. A particular four-digit number N is such that:
(a) The sum of N and 74 is a square; and (b)
The difference between N and 15 is also a
square. What is the number N?
3. Find all positive values of n for which n2+20n +
11 is a (perfect) square.
 DIOPHANTINE EQUATIONS
1. (ax - b)(ay - c) = a 2 xy – ac x – ab y + b 2
2. (x + 1)(y + 1) = xy + x + y + 1
 DIOPHANTINE EQUATIONS
4. Solve for integral solutions 1/x + 1/y = 5/11
5. Solve for integral solutions 1/x + 1/y = 1
6. Solve for integral solutions 3/x + 2/y = 2
7. Solve for integral solutions 7/x + 5/y = 4
8. Solve for integral solutions 1/x + 2/y = 3/19
9. How many positive integer solutions for n
given that the following is also an integer:
n/(100-n)
 DIOPHANTINE EQUATIONS
10. What is the sum of the values of n for which
both n and (n 2 – 9)/(n-1)are integers?
11. Solve the equation 5a – ab = 9b2, where a
and b are positive integers.
 MODULAR ARITHMETIC
• On a digital clock, were we to specify the hour
as “15”, what we’d actually mean is 3 in the
morning. These hours are the same in “modulo
12 arithmetic”, i.e. our numbers are limited to
0 to 12, after which they loop back round. “15
is congruent to 3 modulo/mod 12”
• Let a be an integer and m be a positive integer.
We denote by a mod m the remainder when a
is divided by m.
 CONGRUENT MODULO
Let a and b be integers and m be a positive integer.
We say that a is congruent to b modulo m
if m divides a – b.

We use the notation a  b (mod m) to indicate

that a is congruent to b modulo m.

In other words:
a  b (mod m) if and only if a mod m = b mod m.
 CONGRUENT MODULO
• Let m be a positive integer.
If a  b (mod m) and c  d (mod m),
• then
a + c  b + d (mod m)
ac  bd (mod m).
aK  bK (mod m).
 POLYNOMIAL
• Find a polynomial of degree < 3 passing through (1,2),(3,5),
(5,4).
Solution:
1. Find f1(x) with f1(1) = 2 and f1(3) = f1(5) = 0.
=> f1(x) must have a factor (x-3)(x-5) = c1 (x-3)(x-5)
=> since f1(1)= 2, 2 = c1 (1-3)(1-5)
=> c1 = 2/(1-3)(1-5)
=> f1(x) = 2 (x-3)(x-5) /(1-3)(1-5)
2. Similarly,
f2(x) = 5 (x-1)(x-5) /(3-1)(3-5)
f3(x) = 4 (x-1)(x-3)/(5-1)(5-3)
and F(x) = f1(x) + f2(x) + f3(x) is the solution.
YOU ALL ARE GREAT
THANKS A LOT