Problem-1: Which of the following Diophantine equations cannot be solved – a) 6x + 57y = 22 b) 33x + 14y = 115 c) 14x + 35y = 93 Solution: (a) Applying the Euclidian’s algorithm to the evaluation of gcd(51, 6), we find 51 = 8.6 + 3 6 ...

Read More »## Application of Euclidian’s algorithm in Diophantine equation

Which of the following Diophantine equations cannot be solved – a) 6x + 57y = 22 b) 33x + 14y = 115 c) 14x + 35y = 93 Solution: (a) Applying the Euclidian’s algorithm to the evaluation of gcd(51, 6), we find 51 = 8.6 + 3 6 = 2.3 ...

Read More »## 1st lecture in Primitive roots and indices

Definition of the order of an integer modulo n: Let n > 1 and gcd(a, n) = 1. The order of a modulo n is the smallest positive integer k such that ak ≡ 1 (mod n). Theorem: Let the integer a have order k modulo n. Then ab ≡ ...

Read More »## Euler’s Phi function

Euler’s Phi function: The number of positive integers less than or equal to a positive n and relatively prime to n is denoted by Φ(n). Φ(n) is called the Euler phi function. Theorem: If p is a prime then Φ(p) = p – 1 Proof: If p is a prime, ...

Read More »## Wilson’s theorem of number theory

Proof: Dismissing the case p = 2 and p = 3 as being evident, let us take p > 3. Suppose that a is any of the p – 1 positive integers 1, 2, 3, … , p – 1 and consider the linear congruence ax ≡ 1 (mod p) ...

Read More »## Fermat’s Theorem | number theory

Fermat’s Theorem: Let p be a prime and suppose that p ∤ a. Then ap – 1 ≡ 1(mod p) Proof: We start by considering the first that p – 1 positive multiplies of a; that is the integers a, 2a, 3a, …, (p – 1)a None of this numbers ...

Read More »## For n ≥ 1, established that the integer n(7n^2 + 5) is of the form 6k

Solution: According to division algorithm, we have n = 6q + r ; 0 ≤ r < 6 Let, A = n(7n2 + 5) For r = 0, we have A = n(7n2 + 5) = (6q + r) {7(6q + r)2 + 5} = 6q (7.36q2 + 5) = ...

Read More »## Verify that if an integer is simultaneously a square and a cube, then it must be either of the form 7k or 7k + 1

Proof: Let A be an integer. We have to show that the cube and square of A is of the form 7k or 7k + 1. First we show that, a square is either of the form 7k or 7k + 1. According to the division algorithm, we have A ...

Read More »## Basic properties of congruence and their proved

i) a ≡ b (mod n) Proof: For any integer a, we have 0/n = 0 ⟹ (a – a) / n = 0 ⟹ a – a = 0.n ⟹ a ≡ a (mod n) (proved) ii) If a ≡ b (mod n) then b ≡ a(mod n) ...

Read More »## Congruence

Definition: Let n be a fixed positive integer. Two integers a and b are said to be congruent modulo n, symbolized by a ≡ b (mod n) if divides the difference a – b ; that is, provided that a – b = kn for some integer k. a is ...

Read More »