Placemant Preparation: Tips and Shortcuts on Factors, Multiples, Unit Digit and Last Two Digits of Exponents

Objectives

Factors and Multiples
Prime factorization method
Number of factors of a given number
Number of ways to express a number as the product of two factors
Sum of all the factors of a given number
Number of ways to express a number as the product of two co-prime factors
Euler's $ϕ$

function
Sum of all co-prime factors of given number
LCM and HCF application on Remainders
Factorial and its properties
Largest power of a factor in n!
Unit digit of an exponential expression
Last two digits of an exponential expression

Multiple

If x is a multiple of y, where x and y are natural numbers, then;

\frac{x}{y} = k

, k should be natural number.
In general, if

a

and

b

are any two natural numbers and

\frac{a}{b}

is a natural number, then

\to a

is a multiple of

b

\to b

is a factor of

a

Divisibility

x

is divisible by

y

, where

x

and

y

are any two integers (either positive or negative) and

y \neq 0

, then;

\frac{x}{y} = k

, where

k

is any integer.

16 is a multiple of 4 but not a multiple of -4.
16 is divisible by both 4 and -4.
Note: 0 (zero) is divisible by all integers except '0'.

Important concepts on factors

Concept I: Factors of natural number

Let us consider a number 12. Factors of 12 are 1, 2, 3, 4, 6 and 12. There are 6 factors for 12.
Similarly factors of 30 are 1, 2, 3, 5, 6, 10, 15 and 30. There are 8 factors for 30.
Key points

All perfect squares have an odd number of factors
Perfect square of any prime number has exactly 3 factors
All non-perfect squares have even number of factors
Perfect numbers: If the sum of all factors (except that number itself) of a number is equal to the number itself is called a perfect number

Eg: Factors of 6 except 6

\to

1, 2, 3
Sum of above factors = 1 + 2 + 3 = 6
28 and 496 are the other perfect numbers in the first 1000 natural numbers.

Concept II: Prime factorization

All natural numbers except 1 can be expressed in its prime factorization form. Simply a natural number greater than 1 is the suitable combination of its prime factors.
Eg:

10 = 2^{1} \times 5^{1}

16 = 2^{4}

30 = 2^{1} \times 3^{1} \times 5^{1}

100 = 2^{2} \times 5^{2}

Concept III: Number of factors of a natural number

If 'N' a natural number and

N = a^{p} \times b^{q} \times c^{r} \times

..., where a, b, c... are the distinct prime factors of N and p, q, r... are natural numbers which are representing the occurrence of corresponding prime factors in N.

Number of factors of N (including 1 and N) =

(p + 1) (q + 1) (r + 1)

...

Find the number of factors of 10, 30 100 and 1024

10 = 2^{1} \times 5^{1} \to number of factors = (1 + 1) (1 + 1) = 2 \times 2 = 4

30 = 2^{1} \times 3^{1} \times 5^{1} \to number of factors = (1 + 1) (1 + 1) (1 + 1) = 2 \times 2 \times 2 = 8

100 = 2^{2} \times 5^{2} \to number of factors = (2 + 1) (2 + 1) = 3 \times 3 = 9

1024 = 2^{10} \to number of factors = (10 + 1) = 11

Concept IV: Number of ways to express a number as the product of two factors

If N is a non-perfect square (number of factors should be even)

Then the number of ways to express N as the product of two factors =

\frac{number of factors}{2}

If N is a perfect square

Then the number of ways to express N as the product of any two factors =

\frac{number of factors + 1}{2}

If N is a perfect square

Then the number of ways to express N as the product of two DISTINCT factors =

\frac{number of factors - 1}{2}

Let's take a look at few examples.
Let us consider the number 30, it can be expressed as the product of two factors in the following ways:

1 \times 30

2 \times 15

3 \times 10

5 \times 6

i.e. 30 can be expressed as the product of two factors in 4 ways. This is half the total number of factors of 30. i.e. the total number of factors of 30 is 8.
Consider another number 36, it's factors are: 1, 2, 3, 4, 6, 9, 12, 18, 36 (Total 9 factors)
36 can be expressed as the product of two factors in the following ways:

1 \times 36

2 \times 18

3 \times 12

4 \times 9

6 \times 6

. Hence the number of ways to express 36 as the product of two factors is 5. And the number of ways to express 36 as the product of two DISTINCT factors in 4 ways (excluding

6 \times 6

)

Concept V: Sum of all factors

If 'N' a natural number and

N = a^{p} \times b^{q} \times c^{r} \times

..., where a, b, c... are the distinct prime factors of N and p, q, r... are natural numbers which are representing the occurrence of corresponding prime factors in N.

Sum of all factors of N (including 1 and N)

Sum of all factors of N (including 1 and N) =

(a^{0} + a^{1} + a^{2} + ... + a^{p}) (b^{0} + b^{1} + b^{2} + ... + b^{q}) (c^{0} + c^{1} + c^{2} + ... + c^{r}) ...

[\frac{a^{p + 1} - 1}{a - 1}] [\frac{b^{q + 1} - 1}{b - 1}] [\frac{c^{r + 1} - 1}{c - 1}] ...

Find the sum of all factors of 60?

60 = 2^{2} \times 3^{1} \times 5^{1}

Sum of all factors of 60

= (2^{0} + 2^{1} + 2^{2}) (3^{0} + 3^{1}) (5^{0} + + 5^{1})

= (1 + 2 + 4) (1 + 3) (1 + 5) = 168

Concept VI: Number of ways to express a number as the product of two relatively prime factors

If 'N' a natural number and

N = a^{p} \times b^{q} \times c^{r} \times

..., where a, b, c... are the distinct prime factors of N and p, q, r.... are natural numbers which are representing the occurrence of corresponding prime factors in N.

Then the number of ways to express N as the product of two co-primes =

2^{n - 1}

, where n is the number of distinct prime factors of N.

How many different ways 30 can be expressed as the product of two relatively prime factors ?

30 = 2^{1} \times 3^{1} \times 5^{1}

: There are three distinct prime factors of 3, so

n = 3

∴

Therefore the number of ways to express N as the product of two co-primes

= 2^{3 - 1} = 2^{2} = 4

And the required expressions are

1 \times 30

2 \times 15

3 \times 10

5 \times 6

. Note: 1 is relatively prime to all natural numbers except 1.

Euler's $ϕ$

function or relatively prime to N, which are less than N.

Euler's

ϕ

(phy) function is defined as

ϕ (N) =

the number of all co-primes to N, which are less than N.

If 'N' a natural number and

N = a^{p} \times b^{q} \times c^{r} \times

..., where a, b, c... are the distinct prime factors of N and p, q, r.... are natural numbers which are representing the occurrence of corresponding prime factors in N.

ϕ (N) = N [1 - \frac{1}{a}] [1 - \frac{1}{b}] [1 - \frac{1}{c}]

... `

If p is relatively prime to 24 and p < 24. How many such values are possible for p? OR Find the number of co-primes to 24, which are less than 24.?

24 = 2^{3} \times 3^{1}

ϕ (24) = 24 [1 - \frac{1}{2}] [1 - \frac{1}{3}] = 24 \times \frac{1}{2} \times \frac{2}{3} = 8

Hence there are 8 possible values for p(1, 5, 7, 11, 13, 17, 19, 23).

Concept VIII: Sum of all relatively prime numbers to N, which are less than N.

This is the extension of the above result. Here we are finding the sum of all co-primes to N which are less than N.

Sum = \frac{N^{2}}{2} [1 - \frac{1}{a}] [1 - \frac{1}{b}] [1 - \frac{1}{c}]

... OR

\frac{N}{2} ϕ (N)

Find the sum of all co-primes to 24, which are less than 24.?

Sum = \frac{24^{2}}{2} [1 - \frac{1}{2}] [1 - \frac{1}{3}] = 96

Placemant Preparation

Pages

Tips and Shortcuts on Factors, Multiples, Unit Digit and Last Two Digits of Exponents

Objectives

Multiple

Divisibility

Important concepts on factors

Concept I: Factors of natural number

Concept II: Prime factorization

Concept III: Number of factors of a natural number

Concept IV: Number of ways to express a number as the product of two factors

Concept V: Sum of all factors

Concept VI: Number of ways to express a number as the product of two relatively prime factors

Euler's $ϕ$

function or relatively prime to N, which are less than N.

Concept VIII: Sum of all relatively prime numbers to N, which are less than N.

No comments:

Post a Comment

Blog Archive