3.1 Odd, Even and Divisibility Relationships

Understanding the properties of odd and even numbers, as well as divisibility relationships, is fundamental in number theory. Below is a breakdown of these concepts.

1. Odd and Even Numbers

• Even Numbers: An integer $n$ is called even if it can be expressed as $n=2k$, where $k$ is an integer. Examples: $-4,-2,0,2,4,6$.
• Odd Numbers: An integer $n$ is called odd if it can be expressed as $n=2k+1$, where $k$ is an integer. Examples: $-3,-1,1,3,5$.

Properties:

1. Sum of Two Even Numbers: The sum of two even numbers is even.
   • $2a+2b=2(a+b)$ (where $a,b$ are integers)
2. Sum of Two Odd Numbers: The sum of two odd numbers is even.
   • $(2a+1)+(2b+1)=2(a+b+1)$
3. Sum of an Odd and an Even Number: The sum of an odd and an even number is odd.
   • $(2a+1)+2b=2(a+b)+1$
4. Product of Two Even Numbers: The product of two even numbers is even.
   • $2a\cdot 2b=4ab$
5. Product of Two Odd Numbers: The product of two odd numbers is odd.
   • $(2a+1)(2b+1)=4ab+2a+2b+1=2(2ab+a+b)+1$
6. Product of an Odd and an Even Number: The product of an odd and an even number is even.
   • $(2a+1)\cdot 2b=2(2ab+b)$

2. Divisibility Relationships

Divisibility involves determining whether one integer can be evenly divided by another. The notation $a\mid b$ means that $a$ divides $b$ without leaving a remainder.

Key Concepts:

1. Divisibility Rule:
   • An integer $a$ divides an integer $b$ if there exists an integer $k$ such that $b=ak$.
2. Even and Odd Numbers and Divisibility:
   • An even number is divisible by $2$.
   • An odd number is not divisible by $2$.
3. Divisibility by Other Numbers:
   • Divisibility by 3: A number is divisible by $3$ if the sum of its digits is divisible by $3$.
   • Divisibility by 5: A number is divisible by $5$ if its last digit is $0$ or $5$.
   • Divisibility by 10: A number is divisible by $10$ if its last digit is $0$.
4. Transitive Property:
   • If $a\mid b$ and $b\mid c$, then $a\mid c$.
5. Greatest Common Divisor (GCD):
   • The largest positive integer that divides two or more integers without leaving a remainder.
6. Least Common Multiple (LCM):
   • The smallest positive integer that is divisible by two or more integers.

Example Problems

1. Determine if the sum of 8 and 7 is odd or even:
   • $8$ is even, $7$ is odd.
   • $8+7=15$ (odd).
2. Check the divisibility:
   • Is $24$ divisible by $6$?
   • Yes, because $24=6\times 4$.
3. Calculate GCD and LCM:
   • GCD of $12$ and $18$ is $6$.
   • LCM of $12$ and $18$ is $36$.

3.2 The Divisibility Rules

Divisibility rules help determine whether one integer is divisible by another without performing the actual division. Here are the common divisibility rules for various integers:

1. Divisibility by 2

• Rule: A number is divisible by $2$ if its last digit is even (i.e., $0,2,4,6,8$).

Example:

• $146$ is divisible by $2$ (last digit is $6$).
• $135$ is not divisible by $2$ (last digit is $5$).

2. Divisibility by 3

• Rule: A number is divisible by $3$ if the sum of its digits is divisible by $3$.

Example:

• For $123$: $1+2+3=6$ (divisible by $3$). So, $123$ is divisible by $3$.
• For $124$: $1+2+4=7$ (not divisible by $3$). So, $124$ is not divisible by $3$.

3. Divisibility by 4

• Rule: A number is divisible by $4$ if the last two digits form a number that is divisible by $4$.

Example:

• $312$: Last two digits are $12$ (divisible by $4$). So, $312$ is divisible by $4$.
• $75$: Last two digits are $75$ (not divisible by $4$). So, $75$ is not divisible by $4$.

4. Divisibility by 5

• Rule: A number is divisible by $5$ if its last digit is $0$ or $5$.

Example:

• $250$ (last digit $0$), so $250$ is divisible by $5$.
• $34$ (last digit $4$), so $34$ is not divisible by $5$.

5. Divisibility by 6

• Rule: A number is divisible by $6$ if it is divisible by both $2$ and $3$.

Example:

• $18$: Last digit $8$ (even) and $1+8=9$ (divisible by $3$). So, $18$ is divisible by $6$.
• $20$: Last digit $0$ (even) but $2+0=2$ (not divisible by $3$). So, $20$ is not divisible by $6$.

6. Divisibility by 8

• Rule: A number is divisible by $8$ if the last three digits form a number that is divisible by $8$.

Example:

• $456$: Last three digits $456$ (divisible by $8$). So, $456$ is divisible by $8$.
• $1234$: Last three digits $234$ (not divisible by $8$). So, $1234$ is not divisible by $8$.

7. Divisibility by 9

• Rule: A number is divisible by $9$ if the sum of its digits is divisible by $9$.

Example:

• For $729$: $7+2+9=18$ (divisible by $9$). So, $729$ is divisible by $9$.
• For $123$: $1+2+3=6$ (not divisible by $9$). So, $123$ is not divisible by $9$.

8. Divisibility by 10

• Rule: A number is divisible by $10$ if its last digit is $0$.

Example:

• $100$ (last digit $0$), so $100$ is divisible by $10$.
• $43$ (last digit $3$), so $43$ is not divisible by $10$.

9. Divisibility by 11

• Rule: A number is divisible by $11$ if the difference between the sum of its digits in odd positions and the sum of its digits in even positions is either $0$ or divisible by $11$.

Example:

• For $121$:
  • Odd positions: $1+1=2$
  • Even position: $2$
  • Difference: $2-2=0$ (divisible by $11$). So, $121$ is divisible by $11$.
• For $12345$:
  • Odd positions: $1+3+5=9$
  • Even positions: $2+4=6$
  • Difference: $9-6=3$ (not divisible by $11$). So, $12345$ is not divisible by $11$.

3.3 The Division Algorithm’

The Division Algorithm is a fundamental principle in number theory that describes how integers can be divided by one another. It states that given any two integers $a$ and $b$ (where $b>0$), there exist unique integers $q$ (the quotient) and $r$ (the remainder) such that:

$$a=bq+r$$

where $0\le r<b$.

Components of the Division Algorithm

• Dividend ($a$): The number being divided.
• Divisor ($b$): The number by which the dividend is divided.
• Quotient ($q$): The integer result of the division.
• Remainder ($r$): The part of the dividend that is left over after dividing.

Examples

Example 1: Positive Dividend and Divisor

Let’s consider $a=17$ and $b=5$.

1. Perform the Division:
   • When $17$ is divided by $5$, the quotient $q$ is $3$ (since $5\times 3=15$).
   • The remainder $r$ is $17-15=2$.
2. Verification:
   • According to the division algorithm: $$17=5\cdot 3+2$$
   • The remainder $2$ is less than $5$, satisfying the condition $0\le r<b$.

Example 2: Negative Dividend

Consider $a=-9$ and $b=4$.

1. Perform the Division:
   • When $-9$ is divided by $4$, the quotient $q$ is $-3$ (since $4\times -3=-12$).
   • The remainder $r$ is $-9-(-12)=3$.
2. Verification:
   • According to the division algorithm: $$-9=4\cdot (-3)+3$$
   • The remainder $3$ is less than $4$, satisfying the condition $0\le r<b$.

Properties of the Division Algorithm

1. Uniqueness: The integers $q$ and $r$ are unique for given $a$ and $b$. That means for each pair of $a$ and $b$, there’s only one quotient and one remainder.
2. Range of the Remainder: The remainder $r$ is always non-negative and strictly less than the divisor $b$.

Applications of the Division Algorithm

1. Finding GCD: The Division Algorithm is often used in algorithms for finding the greatest common divisor (GCD) of two integers, such as the Euclidean algorithm.
2. Modular Arithmetic: The concept of remainders leads to modular arithmetic, which is fundamental in computer science, cryptography, and number theory.
3. Polynomial Division: The Division Algorithm can be extended to polynomials, where for any polynomial $P(x)$ and a polynomial $D(x)$ (where $D(x)$ is not zero), there exist unique polynomials $Q(x)$ (the quotient) and $R(x)$ (the remainder) such that:

   $$P(x)=D(x)Q(x)+R(x)$$where the degree of $R(x)$ is less than the degree of $D(x)$.

3.4 The Greatest Common Divisor (GCD) and Euclidean Algorithm

. Greatest Common Divisor (GCD)

The Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides each of the integers without leaving a remainder.

Notation: The GCD of integers $a$ and $b$ is often denoted as $\text{gcd}(a,b)$.

Properties of GCD:

• If $a$ and $b$ are both zero, $\text{gcd}(0,0)$ is typically undefined.
• $\text{gcd}(a,0)=|a|$ for any integer $a$.
• $\text{gcd}(a,b)=\text{gcd}(b,a)$ (commutative property).
• $\text{gcd}(a,b)=\text{gcd}(a,b-ka)$ for any integer $k$.

2. Finding the GCD: Example

Consider $a=48$ and $b=18$.

1. List the Factors:
   • Factors of $48$: $1,2,3,4,6,8,12,16,24,48$
   • Factors of $18$: $1,2,3,6,9,18$
2. Identify Common Factors:
   • Common factors: $1,2,3,6$
3. GCD:
   • The largest common factor is $6$.
   • So, $\text{gcd}(48,18)=6$.

3. Euclidean Algorithm

The Euclidean Algorithm is a method for finding the GCD of two integers using a series of division steps. It is based on the principle that the GCD of two numbers also divides their difference.

Algorithm Steps:

1. Given two integers $a$ and $b$ (with $a>b$), divide $a$ by $b$ and find the remainder $r$:

   $$a=bq+r(0\le r<b)$$where $q$ is the quotient.

2. Replace $a$ with $b$ and $b$ with $r$.
3. Repeat the process until $r=0$. The last non-zero remainder is the GCD.

4. Example Using the Euclidean Algorithm

Let’s find the GCD of $48$ and $18$ using the Euclidean Algorithm.

1. First Division:

   $$48=18\cdot 2+12$$(Quotient $q=2$, Remainder $r=12$)

2. Second Division:

   $$18=12\cdot 1+6$$(Quotient $q=1$, Remainder $r=6$)

3. Third Division:

   $$12=6\cdot 2+0$$(Quotient $q=2$, Remainder $r=0$)

Since the last non-zero remainder is $6$, we have:

$$\text{gcd}(48,18)=6$$

5. Properties of the Euclidean Algorithm

• Efficiency: The Euclidean algorithm is very efficient and can quickly compute the GCD even for large integers.
• Recursion: The algorithm can be expressed recursively, allowing for elegant implementations in programming.

Recursive Formulation:

gcd(a,b)={bif b=0gcd(b,amod  b)otherwise\text{gcd}(a, b) = \begin{cases} b & \text{if } b = 0 \\ \text{gcd}(b, a \mod b) & \text{otherwise} \end{cases}gcd(a,b)={bgcd(b,amodb)​if b=0otherwise​

3.5 Different Base Number System

A number system is a way to represent numbers using a consistent set of symbols and a base. The base (or radix) indicates how many unique digits, including zero, are used to represent numbers. Here’s an overview of some common number systems:

1. Base 10 (Decimal)

• Base: 10
• Digits Used: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
• Description: This is the most common number system used in daily life. Each digit’s place value is a power of $10$.

Example:

• The decimal number $345$ can be expressed as: 3×102+4×101+5×100=300+40+53 \times 10^2 + 4 \times 10^1 + 5 \times 10^0 = 300 + 40 + 53×102+4×101+5×100=300+40+5

2. Base 2 (Binary)

• Base: 2
• Digits Used: 0, 1
• Description: This number system is used in digital electronics and computing. Each digit represents a power of $2$.

Example:

• The binary number $1011$ can be expressed as: 1×23+0×22+1×21+1×20=8+0+2+1=11 (in decimal)1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 8 + 0 + 2 + 1 = 11 \text{ (in decimal)}1×23+0×22+1×21+1×20=8+0+2+1=11 (in decimal)

3. Base 8 (Octal)

• Base: 8
• Digits Used: 0, 1, 2, 3, 4, 5, 6, 7
• Description: This system is used in some computing applications and represents numbers using powers of $8$.

Example:

• The octal number $27$ can be expressed as: 2×81+7×80=16+7=23 (in decimal)2 \times 8^1 + 7 \times 8^0 = 16 + 7 = 23 \text{ (in decimal)}2×81+7×80=16+7=23 (in decimal)

4. Base 16 (Hexadecimal)

• Base: 16
• Digits Used: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F (where A=10, B=11, …, F=15)
• Description: Commonly used in computing as a more human-readable representation of binary-coded values. Each digit represents a power of $16$.

Example:

• The hexadecimal number $2F$ can be expressed as: 2×161+15×160=32+15=47 (in decimal)2 \times 16^1 + 15 \times 16^0 = 32 + 15 = 47 \text{ (in decimal)}2×161+15×160=32+15=47 (in decimal)

5. Base 60 (Sexagesimal)

• Base: 60
• Digits Used: 0 to 59
• Description: This system is used in measuring time (seconds and minutes) and angles (degrees).

Example:

• The time $2:30$ can be thought of as:
  • 2×601+30×600=120+30=150 (in minutes)2 \times 60^1 + 30 \times 60^0 = 120 + 30 = 150 \text{ (in minutes)}2×601+30×600=120+30=150 (in minutes)

Conversion Between Bases

1. Decimal to Binary:

To convert a decimal number to binary, divide the number by $2$ and record the remainder. Continue dividing the quotient until it reaches $0$. The binary representation is the remainders read in reverse order.

Example: Convert $13$ to binary:

• $13÷2=6$ remainder $1$
• $6÷2=3$ remainder $0$
• $3÷2=1$ remainder $1$
• $1÷2=0$ remainder $1$

Reading in reverse: $1101$ (binary).

2. Binary to Decimal:

To convert binary to decimal, multiply each digit by its corresponding power of $2$.

Example: Convert $1101$ to decimal:

• 1×23+1×22+0×21+1×20=8+4+0+1=13 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 8 + 4 + 0 + 1 = 131×23+1×22+0×21+1×20=8+4+0+1=13

3.6 Modular Arithmetic

Modular arithmetic, often referred to as “clock arithmetic,” is a system of arithmetic for integers where numbers wrap around upon reaching a certain value, called the modulus. It is particularly useful in computer science, cryptography, and number theory.

1. Definition

Given two integers $a$ and $b$, and a positive integer $n$ (the modulus), we say that $a$ is congruent to $b$ modulo $n$ if $n$ divides the difference of $a$ and $b$. This is denoted as:

$$a\equiv b\mathrm{mod}n$$

This means:

$$a-b=kn\text{for some integer }k$$

2. Examples of Modular Arithmetic

Example 1: Basic Congruences

• Calculate $17\mathrm{mod}5$: $$17÷5=3\text{(quotient)}$$ $$17-5\times 3=17-15=2$$ Thus, $17\equiv 2\mathrm{mod}5$.

Example 2: Larger Numbers

• Calculate $23\mathrm{mod}7$: $$23÷7=3\text{(quotient)}$$ $$23-7\times 3=23-21=2$$ Thus, $23\equiv 2\mathrm{mod}7$.

3. Properties of Modular Arithmetic

1. Reflexivity:

   $$a\equiv a\mathrm{mod}n$$

2. Symmetry:

   $$a\equiv b\mathrm{mod}n⟹b\equiv a\mathrm{mod}n$$

3. Transitivity:

   $$a\equiv b\mathrm{mod}n\text{ and }b\equiv c\mathrm{mod}n⟹a\equiv c\mathrm{mod}n$$

4. Addition:

   $$a\equiv b\mathrm{mod}n\text{ and }c\equiv d\mathrm{mod}n⟹(a+c)\equiv (b+d)\mathrm{mod}n$$

5. Subtraction:

   $$a\equiv b\mathrm{mod}n\text{ and }c\equiv d\mathrm{mod}n⟹(a-c)\equiv (b-d)\mathrm{mod}n$$

6. Multiplication:

   $$a\equiv b\mathrm{mod}n\text{ and }c\equiv d\mathrm{mod}n⟹(a\cdot c)\equiv (b\cdot d)\mathrm{mod}n$$

7. Exponentiation:

   a≡bmod  n  ⟹  ak≡bkmod  nfor any integer ka \equiv b \mod n \implies a^k \equiv b^k \mod n \quad \text{for any integer } ka≡bmodn⟹ak≡bkmodnfor any integer k

4. Applications of Modular Arithmetic

1. Cryptography: Modular arithmetic is fundamental in various cryptographic algorithms, such as RSA encryption, which relies on properties of prime numbers and modular operations.
2. Computer Science: Used in hashing functions, random number generation, and algorithms that require cyclical behavior (e.g., round-robin scheduling).
3. Congruences: Solving problems that involve finding numbers that satisfy certain conditions, such as the Chinese Remainder Theorem.
4. Clock Arithmetic: Timekeeping is a practical example of modular arithmetic where time wraps around after reaching a certain point (e.g., 12-hour clocks).

5. Solving Modular Equations

To solve equations of the form $ax\equiv b\mathrm{mod}n$:

1. Identify the integers $a$, $b$, and $n$.
2. Find the multiplicative inverse of $a$ modulo $n$ if $a$ and $n$ are coprime (i.e., $\text{gcd}(a,n)=1$).
3. Multiply both sides of the equation by this inverse to isolate $x$.

Example: Solve $3x\equiv 6\mathrm{mod}11$.

1. Identify: $a=3$, $b=6$, $n=11$.
2. Find the inverse of $3\mathrm{mod}11$: The inverse is $4$ (since $3\cdot 4\equiv 1\mathrm{mod}11$).
3. Multiply both sides: $$4\cdot (3x)\equiv 4\cdot 6\mathrm{mod}11\Rightarrow x\equiv 24\mathrm{mod}11\Rightarrow x\equiv 2\mathrm{mod}11$$