practice problems pending CRT homework

Q1.
Let n be the least positive integer greater than 1000 for which gcd(63,n+120) = 21 and gcd(n+63,120) = 60. What is the sum of digits of n?

S1.

First wrong attempt:
n = 21p - 120 = 60q - 63
=> q = (7p - 19)/20
p = 17 works between p = 1 to 20.
So p = 17 mod 20.
p = 17,37,57,77,97...
21p - 120 >= 1000
=> p>=880/21
=> p = 57
=> q = 19
n = 21*57-120 = 1077

sum_digits(n) = 15

Why is this wrong?
gcd(63, 1077 + 120) = 63 not 21.

gcd(63, n + 120) = 21
means that
gcd(63/21,(n+120)/21) = 1
gcd(3,p) = 1
=> p can't be a multiple of 3 but we chose 57.

Similarly:
gcd(n+63,120) = 60
=>
gcd((n+63)/60,2) = 1
=> gcd(q,2) = 1 => q is odd.

So coming back to:
q = (7p - 19)/20
for p = 77, q = (77*7 - 19)/20 = 26 but q has to be odd.
for p = 97, q = (97*7 - 19)/20 = (630 + 49 - 19)/20 = 660/20 = 33. It works.
So,
n = 60*33 - 63 = 1980 - 63 = 1917
sum_digits(n) = 18

Q2. Prove that 10^(3n+1) cannot be represented as a sum of 2 cubes(integers).
S2.
Typically when dealing with cubes and modular arithmetic, we prefer 7 or 9 to take mod.
Why?
Every cube leaves -1,0,1 as remainder with 7 or 9.

10^(3n+1) = 1 mod 9
If it's equal to a^3 + b^3 then it's possible to generate 1 on RHS.
So we can't disprove it.

Let's try with 7.
10^3 = -1 mod 7
(10^3)^n*10 = -1^n*3 mod 7 = -3 or 3 mod 7 = 3 or 4 mod 7
a^3 + b^3 mod 7 can be 0,-1,-2,1,2 = 0,1,2,5,6
H.P.

Q3.


S3.
3n^3 + 12n^2 + 13n + 2 mod 2 = n^3 + n^2 + n = n(n^2 + n + 1) = 0 mod 2 for both cases (n=0,1 mod 2)
So any 'n' works for mod 2.

3n^3 + 12n^2 + 13n + 2 mod 3 = n + 2 mod 3
= 0 => n = 1 mod 3

3n^3 + 12n^2 + 13n + 2 mod 5 = 3n^3 + 2n^2 + 3n + 2 = n^2(3n + 2) + 1(3n+2) = (n^2 + 1)(3n + 2)
n = 0 mod 5, doesn't work
n = 1 mod 5 works
n = 2 mod 5 works
n = 3 mod 5 works
n = 4 mod 5 doesn't work

So 
n = 1 mod 3
n = 1,2,3 mod 5
So there are 3 unique solutions mod 15, and hence 6 solutions mod 30.

Without CRT:
List values of n till 30 which are 1 mod 3:
1,4,7,10,13,16,19,22,25,28
From this list:
1,7,1316,22,28 work
So answer is is n = 1,7,1316,22,28 mod 30


Let's solve each using CRT: (1 mod 3, 1 mod 5)
n = a.3 + b.5
mod 3
1 = 2b mod 3 => b = 2
mod 5
1 = 3a mod 5 => a = 2
n = 16 mod 15 = 1 mod 15

1 mod 3, 2 mod 5
mod 3 => b = 2 as earlier
mod 5
2 = 3a mod 5 => a = 4
n = 12 + 10 = 22 mod 15 = 7 mod 15

1 mod 3, 3 mod 5
b = 2
3 = 3a mod 5 => a = 1
n = 3 + 10 = 13 mod 15


Q4.
Obtain the 2 incongruent solutions mod 210:
2x = 3 mod 5
3x = 2 mod 7
4x = 2 mod 6
S4.

2x = 3 mod 5 => x = 4 mod 5

3x = 2 mod 7 => 6x = 4 mod 7 => x = -4 = 3 mod 7

4x = 2 mod 6 => -2x = 2 mod 6 => -x = 1 mod 3 => x = 2 mod 3 => x = 2,5 mod 6

Using CRT now gives us 59 and 164. 

Q5.
A band of 17 pirates stole a sack of gold coins. When they tried to divide the fortune into equal portions, 3 coins remained. In the ensuing brawl over who should get the extra coins, one pirate was killed. The wealth was redistributed, but this time an equal division left 10 coins. Again an argument developed in which another pirate was killed. But now the total fortune was evenly distributed among the survivors. What was the least number of coins that could have been stolen?
S5.

n = 0 mod 15
n = 10 mod 16
n = 3 mod 17

n = a.15.16 + b.16.17 + c.17.15
mod 15
0 = b.16.17 => b = 15 so we can actually ignore the 'b' term since it will take the sum above the lcm(15,16,17)

mod 17
3 = a.(-2)(-1) mod 17 = 2a
2a = 3 mod 17 => a = 10

mod 16
10 = -c mod 16
c = 6 mod 16

n = 15.16.10 + 6.17.15 = 30(51 + 80) = 131*30 = 3930
15*16*17 = 4080
So n = 3930

Q6.

S6.
Simply use CRT:
x = 99 mod 210

Q7.
Let n be a natural number such that n+1 is divisible by 24. Prove that the sum of all the divisors of n is also divisible by 24.
S7.

24| n + 1 
=> n is odd
Also n is not div by '3'.
So each divisor of n is also odd and not div by 3.

Is 'n' a perfect square?
n = 2k +1 since it's odd.
every odd integer square = 1 mod 8.
n = 24k - 1
=> n = -1 mod 8 = 7 mod 8
So n is not a square => it has an even number of divisors which can be split into pairs.

sum of divisors = d1 + n/d1 + d2 + n/d2 ...

Let's look at first pair
d1 + n/d1 = (d1^2 + n)/d1______[1]
As we said earlier d1 is odd and not div by 3.
d1 = -+1 mod 3
d1^2 = 1 mod 3
d1^2 = 1 mod 8 since it's odd.

Since 3,8 are co-prime d1^2 = 1 mod 24
Numerator of [1] = 1 + -1 = 0 mod 24
So numerator is div by 24.
And denominator doesn't cancel out any factor of 24 since it's co-prime to 24.
And since this sum is an integer it means that this sum is divisible by 24.

Since each pair is div by 24, entire sum is too. Hence proved.







Comments

Post a Comment

Popular posts from this blog

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

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