practice problems pending 1,2,4,7

 


Homework(proofs):
Q1.


S1.
n = 1 => (2k+1)^(2^1) = 4k^2 + 4k + 1 = 4k(k+1) + 1 = 8p + 1 = 1 mod 2^3(since k(k+1) is even)
So works for n = 1
Assume
(2k+1)^(2^n) = 1 mod 2^(2^(n+2)) _____[1]
and using this prove for n+1:
(2k+1)^(2^(n+1)) = 1 mod 2^(2^(n+3))
LHS = (2k+1)^(2^n.2^1) = [(2k+1)^(2^n)]^2 = [2^(n+2).m + 1]^2 using [1]
= 1 + 2.m.2^(n+2) + m^2.[2^(n+2)]^2 = 1 + m.2^(n+3) + m^2.2^(2n+4)
If you take mod 2^(n+3), it's clearly 1.
H.P.




Q2.

Call a natural number n convenient, if n^2 + 1 is divisible by 1000001 . Prove that among the numbers   1,2,…,1000000, there are evenly many "convenient" numbers.

S2.
So essentially we need to find some sort of complement for each 'n' satisfying this.
If we can show that for each 'n' satisfying this, there is another number satisfying this, we are done.
Simplest 'complement' here is -n but that's negative.
So let's think circular and try N-n where N = 1000,001

(N-n)^2 +1 = N^2 + n^2 - 2N.n + 1 = n^2 + 1 + N(N-2n)
Here n^2 + 1 is div by N and N(N - 2n) as well.
So for every 'n' we have shown a complement exists within 1...N-1.

But is it possible that N-n = n? In that case we get stuck.
No, since N = 2n and N is odd, so that's not possible.

Q3.
Pr. th. 30^99 + 61^100 is div by 31.

S3.
30 = 61 =  -1 mod 31
=> -1^99 + -1^100 = 0 mod 31
H.P.

Q4.



S4.
(a)
5^2 = 4 mod 7
2^5 = 4 mod 7
=> 4^n[1 + 3/4] = 4^(n-1)*7 divisible by 7.
H.P.

(b)
3^n = 16^n = 3 mod 13
=> 9.3^n + 16^n.4 = 3^n*13 div by 13

(c)
= 32^n.2 + 25.5^n
= 5^n.2 + 25.5^n
= 0 mod 27 H.P.
Since
32 = 5 mod 27
25 = - 2 mod 27

Q5.
What is remainder of 10 + 100 + 1000 ... 10^10 mod 7
S5.

10^1 = 3 m 7

10^2 = 2 m 7

10^3 = 3*2 m 7 = -1

10^6 = 1 m 7


10^10 = 10^6*10^4 = -10 = 4 m 7

Every power of 10^n = 4 mod 6 for n>=1

Why?

10^1 = 4 mod 6

10^2 = 4*10 = 40 = 4 mod 6

...


So the given expression becomes

10^4 + 10^4 .. 10 times

But 10^4 mod 7 = 4

=> 10*4 = 40 = 5 mod 7

Q6.

Pr. th. 11^(n+2) + 12^(2n+1) is divisible by 133 for any natural number n.

S6. Method 1: 11^(n+2) + 12^(2n+1) = 121.11^n + 12.144^n 144^n = 11^n mod 133 So expr becomes: 11^n(121+12) which is div by 133 H.P. Method 2:

133 = 7*19

So we will show div by 7,19 individually.

11^(n+2) + 12^(2n+1) = 121.11^n + 12.144^n

121.11^n + 12.144^n mod 7 = 121.4^n + 12. 4^n = 4^n.133 which is div by 7.


Similarly,

121.11^n + 12.144^n mod 19 = 121.11^n + 12. 11^n = 11^n.133 which is div by 19.

H.P.
Q7. Positive integers a,b, and c are randomly and independently selected with replacement from the set {1,2,3,…,2010}. What is the probability that abc+ab+a is divisible by 3? S7.

abc + ab + a = a (1 + b + bc) For it to be div by 3, there are 2 cases. Case 1: a is div by 3. Probability = 1/3 Since 2010 is perfectly div by 3.


Case 2:

a is not div by 3. Prob: 2/3 And 1 + b + bc is div by 3 => b + bc = -1 mod 3 = 2 mod 3 b(1+c) = 2 mod 3 Sub case 1: b = 2 mod 3 and 1+c = 1 mod 3 => Prob: 1/3*1/3 = 1/9 Sub case 2: b = 1 mod 3 and c = 0 mod 3 => Prob: 1/3*1/3 = 1/9 Total Case 2 prob = 2/3*[1/9 + 1/9] = 4/27 Total prob = 1/3 + 4/27 = 13/27 = answer

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