CAT exam preparation videos 2024 | Number System | Remainders 3

Name: CAT exam preparation videos 2024 | Number System | Remainders 3
Uploaded: 2019-07-30T14:30:23.000Z
Duration: 1 h 8 min 29 s

Introduction to ULS Theorem

Overview of the Class

Ray Brakash introduces the third class on Reminders, focusing on the ULS theorem for efficient problem-solving.

Emphasis is placed on understanding how to calculate the ULAR number, which is crucial for applying the theorem effectively.

Understanding ULAR Number

The ULAR number consists of numbers less than 'n' that are coprime to 'n'.

Coprime numbers are defined as having no common factors other than 1 (e.g., 4 and 9; 5 and 6).

Examples illustrate non-coprime pairs, such as 12 and 10, which share a common factor of 2.

Deriving the Formula for ULAR Number

Problem-Solving Approach

A practical example is presented: finding numbers from 1 to 30 that are not multiples of 3.

Calculation shows there are ten multiples of 3 in this range; thus, there are twenty numbers not multiples of three (30 - 10).

Mathematical Representation

The formula can be expressed as 30 times (1 - 1/3), simplifying calculations for identifying non-multiples.

Extending Concepts with Additional Examples

Further Applications

Another example involves calculating numbers from 1 to 50 that are not multiples of five using similar logic.

This leads to a conclusion that there are forty numbers not multiples of five in this range.

Combining Conditions

The discussion progresses to find numbers from 1 to 30 that are neither multiples of two nor five.

Final Steps in Derivation

Elimination Process

To eliminate multiples systematically, first identify those not multiple by two (15 remaining), then exclude those also divisible by five.

Understanding Euler's Totient Function

Counting Numbers Not Multiples of 2 or 5

The speaker calculates the count of numbers from 1 to 30 that are neither multiples of 2 nor multiples of 5, arriving at a total of 12 such numbers.

The identified numbers include: 1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, and 29. This illustrates how to systematically identify non-multiples within a range.

The concept is extended to find numbers from 1 to 60 that are not multiples of 2, 3, or 5, emphasizing the methodical elimination process.

Applying the Euler Number Formula

To calculate the count for numbers from 1 to 60, the formula used is 60 times (1 - 1/2) times (1 - 1/3) times (1 - 1/5).

After performing calculations with this formula yields an answer of 16, indicating there are 16 numbers in this range that are co-prime to both 2, 3, and 5.

Understanding Co-Primality with Euler's Totient Function

The term "Euler number" refers specifically to counting all integers less than a given number (60) that are co-prime with it.

Prime factorization reveals that 60 = 2^2 times 3^1 times 5^1, which helps in understanding which multiples need elimination.

Elimination Process for Co-Primality

By eliminating all multiples of prime factors (2, 3, and 5), we can determine which remaining numbers are co-prime with 60.

It’s emphasized that only prime factors matter; powers do not need consideration since eliminating multiples inherently removes higher powers as well.

Final Calculation Examples

For calculating Euler's number for 60, one must consider only its prime factors: 2, 3, and 5.

Using the same elimination method leads us back to confirming that Euler's number for 60 is indeed calculated as being equal to 16.

Exploring Further Examples

When calculating Euler's number for another example like 10, it involves identifying its prime factors (2, and 5) leading again through similar steps resulting in an answer of 4.

Understanding Euler's Number and Its Applications

Introduction to Co-primality

The number one is unique as it is a multiple of every number and co-prime with every number.

Examples of co-prime pairs include (1, 10), (3, 10), (7, 10), and (9, 10).

The Euler number for 10 is determined to be 4, indicating there are four numbers less than 10 that are co-prime with it: 1, 3, 7, and 9.

Calculating Euler's Number

To find the Euler number for any integer n , we need to identify how many integers less than n are co-prime with n .

For example, calculating the Euler number for 420 involves identifying its prime factors: 2, 3, 5, and 7.

Steps in Calculation

The calculation process includes eliminating multiples of each prime factor from the total count.

After eliminating these multiples from the set of numbers below 420, the result shows that there are exactly 96 numbers that remain co-prime with 420.

General Formula for Euler's Number

The formula for calculating the Euler number can be expressed as:

[ phi(n) = n left(1 - 1/p_1right)left(1 - 1/p_2right)...]

where p_1, p_2,... are the prime factors of n .

Special Cases: Prime Numbers

For a prime number p , its Euler number is simply calculated as p - 1 .

For instance, since all numbers before a prime like 7 (which has six preceding integers: 1,2,3,4,5,6) are co-prime with it.

Conclusion on Co-Primality

One remains an essential part of understanding co-primality; it is neither prime nor composite but serves as a universal co-prime.

This concept extends to any integer greater than one when considering pairs like (one,n).

Application in Remainders

Understanding U-Level Theorem and Its Applications

Introduction to U-Level Theorem

The U-level theorem is a mathematical principle that can solve 90% of questions related to modular arithmetic, with the remaining 10% requiring the Chinese Remainder Theorem.

For applying the U-level theorem, the expression must be in the form x^a mod b , where x and b are co-prime.

Application Example: Finding Remainders

An example is given where we need to find the remainder of 11^62 mod 7 . First, confirm that 11 and 7 are co-prime.

To apply the theorem, calculate 11 mod 7 , which gives a remainder of 4. Then compute 62 mod (p-1) = 6.

Step-by-Step Calculation

Since p = 7 , its U-level is calculated as p - 1 = 6. Thus, we evaluate (11^62) mod 7.

After calculating, we find that (4^2) =16; dividing by 7 gives a final remainder of 2 for this calculation.

Another Example: CAT Question

A previous CAT question involves finding the remainder of 69^282 mod 29. Again, check if both numbers are co-prime.

Here, since both numbers are co-prime, apply U-level theorem: calculate 69 mod 29, yielding a result of 11.

Further Calculations

Next step involves calculating powers; thus we compute 282 / (p -1), leading us to evaluate further remainders.

Continuing from earlier calculations leads us to find that after several steps, the final answer for this example is 5.

More Complex Examples

Another example presented is finding the remainder for 97^97 mod 10. Confirming again that they are co-prime allows application of U-level theorem.

Calculate Euler's totient function for non-prime bases like ten requires eliminating multiples of its prime factors.

Final Steps in Calculation

After determining all necessary remainders through calculations involving powers and divisions by their respective moduli, we conclude with an answer of 7 for this case.

Practice Problem: Additional Example

A practice problem involves calculating 39^128 mod25. Confirming coprimality allows direct application once more.

Understanding Remainders and Their Applications in Mathematics

Exploring the Concept of Remainders

The speaker discusses how to approach a mathematical problem involving remainders, specifically focusing on the square of 14, which is 196.

The positive remainder when dividing 196 by 25 is identified as 21, while the negative remainder is noted as -4. This highlights the dual nature of remainders in division.

The calculation process for finding remainders is elaborated upon, emphasizing that understanding both positive and negative remainders can simplify problems.

Simplifying Calculations with Powers

The speaker explains that when dealing with even powers, such as raising -4 to an even exponent, the negative sign disappears, making calculations easier.

Further simplification techniques are discussed; for instance, breaking down powers like 4^4 into manageable parts (e.g., 16 or 256) aids in calculating remainders effectively.

Practical Applications of Remainder Concepts

The discussion transitions to practical applications of these concepts in solving mathematical problems using theorems like Fermat's Little Theorem and its relevance to competitive exams such as CAT.