practice problems

Q1. Does there exist an integer x satisfying the following conditions?
10x = 1 mod 21
5x = 2 mod 6
4x = 1 mod 7
S1.

No.
Why?
[1] => 
10x = 1 mod 21
=> 10x = 1 mod 3 and 10x = 1 mod 7
=> x = 1 mod 3 and 3x = 1 mod 7 => 36x = 12 mod 7 => x = 5 mod 7
So we have
x = 1 mod 3 and x = 5 mod 7

[2] => 
5x = 2 mod 6
=> 5x = 6k + 2
=> 5x = 2 mod 3 => 2x = 2 mod 3 => 4x = 4 mod 3 => x = 1 mod 3
And
5x = 0 mod 2 => x = 0 mod 2

So we have
x = 1 mod 3
x = 5 mod 7
x = 0 mod 2

[3] =>
4x = 1 mod 7 =>
8x = 2 mod 7 =>
x = 2 mod 7

Which is a contradiction to existing solutions.

Q2. For how many n between 1 and 2520 do we have n^3 = 1 mod 2520?
S2.

2520 = 2^3 * 3^2 * 5 * 7
So
n^3 = 1 mod 8 => n = 1 mod 8
n^3 = 1 mod 9 => n = 1,4,7 mod 9
n^3 = 1 mod 5 => n = 1 mod 5
n^3 = 1 mod 7 => n = 1,2,4 mod 7


For each of those options there is a unique solution (using CRT) between 1 and 2520.
So total 9 valid solutions.

Q3.

Find positive integers a,b,c <= 475 s.t.

a≡0(mod25),a≡1(mod19)

b≡1(mod25),b≡0(mod19)

c≡10(mod25),c≡4(mod19)

S3.
a = 25k = 1 mod 19 = 6k => 18k = 3 mod 19 => -k = 3 mod 19 => k = -3 mod 19 => k = 16
=> a = 400.

b = 19k = 1 mod 25 => -6k = 1 => -24k = 4 mod 25 => k = 4 mod 25 => b = 19*4 = 76

For 'c', we will use CRT:
c = p*19 + q*25
10 = 19p mod 25
=> p = 15
4 = 25q mod 19 = 6q
12 = 18q mod 19 = -q
=> q = -12 = 7 mod 19

c = 7*25 + 15*19 = 175 + 285 = 460

Q4.
Find 2^4034 mod 1000.
S4.
If 2 and 1000 were co-prime we could have simply applied Euler totient theorem to get the answer here.
But they are not.
So we break down 1000 into 125*8 so that 2,125 are co-prime.

1000 = 125*8 = 5^3 * 2^3
Let X = 2^4034.
2^4034 = 0 mod 8
2^4034 = k mod 125(we need to still find 'k')
Once we find 'k', then we apply CRT.
Why CRT?
Since CRT guarantees that there is a unique solution for X modulo (125*8) between 0 to 999(125*8-1).

Using Euler-totient theorem:
2^phi(125) = 1 mod 125 since 2 and 125 are co-prime.
phi(125) = 125*(1-1/5) = 100
2^100 = 1 mod 125
=> 2^4034 = 2^34 mod 125
2^10 = 1024 = 24 mod 125
2^34 = 24*24*24*16 mod 125 = 76*24*16 = 76*9 = 684 = 59 mod 125

So
2^4034 = 0 mod 8
2^4034 = 59 mod 125
2^4034 = 125k + 59
125k + 59 = 0 = 5k + 3 mod 8
=> 5k = -3 mod 8 => 5k = 5 mod 8 => k = 1 mod 8
2^4034 = 125k + 59 = 184 = answer

Q5. Determine last 3 digits of 374^2022.
S5.
Again to compute modulo 1000, we will break it down in 125,8.
374 mod 125 = -1
374^2022 mod 125 = +1

374 mod 8  = -2
374^2022 mod 8 = (-2)^2022 = 0 mod 8

X = 125k + 1 = 0 mod 8
=> 5k = -1 mod 8
=> 25k = -5 mod 8 = k => k = 3
X = 125*3 + 1 = 376 = Answer.

Comments

Post a Comment

Popular posts from this blog

Simon's factoring trick(complete the rectangle)

  "Complete the Rectangle" , also called Simon’s Favorite Factoring Trick , is a clever algebraic method for factoring expressions of the form: x y + a x + b y + c xy + ax + by + c Or more commonly, you'll see it used in a simpler form: x y + a x + b y + d xy + ax + by + d But especially when we’re given something like: x y + a x + b y + a b xy + ax + by + ab It becomes very easy to factor. Let me walk you through it step-by-step. 💡 The Key Idea We add and subtract a constant to turn the expression into a perfect rectangle (a.k.a. a factorable quadratic or product of binomials). The “complete the rectangle” version of this trick usually works best on expressions like: x y + a x + b y + a b xy + ax + by + ab We treat it like this: x y + a x + b y + a b = ( x + b ) ( y + a ) xy + ax + by + ab = (x + b)(y + a) ✅ Step-by-Step Example Factor: x y + 3 x + 2 y + 6 xy + 3x + 2y + 6 Step 1: Rearrange the terms: Group like this: x y + 3 x + 2 y + 6 xy + 3x + ...
Read more

IOQM 2023 solutions

Image
Q1. Let n be a positive integer such that 1 ≤ n ≤ 1000 . Let M n be the number of integers in the set X n = { 4 n + 1 , 4 n + 2 , … , 4 n + 1000 } . Let a = max ⁡ { M n : 1 ≤ n ≤ 1000 } , and b = min ⁡ { M n : 1 ≤ n ≤ 1000 } . a = \max\{M_n : 1 \leq n \leq 1000\}, \quad \text{and} \quad b = \min\{M_n : 1 \leq n \leq 1000\}. Find a − b a - b . Solution: Quick tip: If n^2 = k then (n+1)^2 = k + (2n + 1) We will use this here. Also as the numbers grow larger the gap between 2 perfect squares becomes less and less. For. e.g. there are 10 perfect squares between 1 and 100 but only 4 perfect squares between 101 and 200. So X1 = {sqrt(5) ... sqrt(1004)} will have the most number of perfect squares. While X1000 = {sqrt(4001)...sqrt(5000)} will have the least. In X1 the first integer square root is 3 and we know that 1024 is the square of 32 so the last integer will be 31. Total: 31 - 3 + 1 = 29 integers in X1. In X1000, We know that 64^2 = 4096 so 64 is the first integer. 70^2 = 4900 and ...
Read more

IOQM 2024 Paper solutions (Done 1-21, 29)

Image
Q1 (number-theory). The smallest positive integer that does not divide 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 is: Solution : This product has all the integers from 1 to 9. So smallest integer not dividing it would be the next prime after 9. Which is 11. Answer: 11 Q2 (combinatorics): The number of four-digit odd numbers having digits 1, 2, 3, 4, each occurring exactly once, is: Solution: Last digit has to be 1 or 3: 2C1 Choosing remaining 3 digits: 3C3 Arranging those 3 digits: 3! Answer: 2C1*3C3*3! = 12 Q3 (number-theory): The number obtained by taking the last two digits of \(5^{2024}\) in the same order is: Solution: To get last 2 digits from number, divide by 100 and take the remainder. So we have to compute mod 100. 25 mod 100 = 25 25.5 mod 100 = 125 mod 100 = 25 5^3.5 mod 100 = 25.5 mod 100 = 25 5^4.5 mod 100 = 25.5 mod 100 = 25 ..... So: 5^2024 mod 100 = 25. Q4 (geometry): Let ABCD be a quadrilateral with \(\angle ADC = 70^\circ\), \(\angle ACD = 70^\circ\), \(\angle ACB = 10^\circ\...
Read more