Posts

Number theory test pending

Q1. Does there exist a natural number “(n)” such that (n^2 + n + 1) is divisible by (1955)? If “Yes”, provide an example and if “No”, provide a valid proof. S1. n^2 + n + 1 = 0 mod 5 (if it's div by 1955, it's also div by 5) n^2 + n = 4 mod 5 Let's check all possible remainders of n with 5. n = 0 mod 5 No. n = 1 no. n = 2 4 + 2 = 1 mod 5 n = 3 9 + 3 = 2 mod 5 n = 4 16 + 4 = 0 mod 5 So nothing works. "No". Q3. Using the properties of congruences, prove that 89 | 2^44 - 1 and 97 | 2^48 - 1 S3. 2^44 - 1= 0 mod 89 (2^11 - 1)(2^11 + 1)(2^22 + 1) = 0 mod 89 Since 89 is a prime, one of these factors has to be a multiple of 89. Let's test one by one. 2^11 = 1 mod 89. 2^5.2^6.3 = 3 mod 89 96.64 = 3 mod 89 = 7.64 = 448 = 3 mod 89 H.P. Part 2: 2^48 - 1 = 0 mod 97 = (2^6 - 1)(2^6 + 1)(2^12 + 1)(2^24 + 1) First 2 factors are small. Next: 2^12 + 1 = 0 => 2^12 = -1 mod 97 = 96 mod 97 = 32.128 => 128 = 3 mod 97 which is wrong Next: 2^24 = -1 = 96 mod 97 2^19 = 3 mod 97 ...
Post a Comment
Read more

practice problems pending

Image
Q1)   A square of dimension (n-1) * (n-1) is divided into (n-1)^2 unit squares in the chess board manner. Now, each of these (n^2) vertices of these squares are to be painted black or blue such that each unit square has exactly two black vertices. In how many ways can this be done? S1. Look at an individual square. There are 2 ways for it to yield 2 black vertices. One horizontal edge blue(or black), other black(or blue). Or 1 color each on top edge, and similarly on bottom edge. Once you expand the pattern, there will be only 2 ways to get it done. Each row alternates or each column alternates or both alternate. Case 1: Each row alternates. So each row can start with one of 2 colors and then the pattern is fixed. So 2^n ways since there are 'n' rows. Case 2: Each column alternates. 2^n again. Case 3: Both alternate. Exactly 2 ways like a chessboard. Total: 2^n.2 - 2 = 2^(n+1) - 2. Q2. S2. As the diagram shows a 2x2 bounding box can hold 2 different squares. That rule actually ...
Post a Comment
Read more

Fermat's Theorem on Sums of Two Squares

 If an odd prime number leaves remainder of 1 when divided by 4 then it can be expressed as sum of two integer squares and those 2 integers will be unique for this prime. Examples:  17 = 16 + 1 29 = 25 + 5 41 = 25 + 16 1013 = 22^2 + 23^2
Post a Comment
Read more

practice problems

Q1.  Find the number of triangles whose angular points are at the angular points of a given polygon of (n) sides, but none of its sides are the sides of the polygon. S1. Simple application of  Kaplansky's first lemma . Formula derived is: (n-k-1)C(k-1) + (n-k)C(k) Here k = 3 (n-4)C(2) + (n-3)C(3) = (n-4)(n-5)/2 + (n-3)(n-4)(n-5)/6 = (n-4)(n-5)/2[1 + (n-3)/3] = n(n-4)(n-5)/6
Post a Comment
Read more

number 2026 properties

1. Is 2026 a semiprime(product of only 2 primes)? Yes 2. Is 2026 a deficient number(sum of its proper divisors is less than the number itself)? Yes 3. Is it a happy number? If you keep squaring the digits and adding and then repeating - does it reduce to 1? Yes 4. Is it sum of 2 squares? 45^2 + 1^2 5. Is 1013 sum of 2 squares? = 22^2 + 23^2 ( Fermat theorem on sum of 2 squares )
Post a Comment
Read more

practice problems

Q1. (n) is a positive integer. (A) is a set such that A={1,2,...,n}. Let (t_n) denote the number of subsets of (A) such that the arithmetic mean (AM) of the elements is an integer. Prove that (t_n) and (n) are both odd or both even. S1. 1. Let us ignore empty subset since A.M. is not defined for that. 2. Subsets of size 1: {1}, {2} ... {n}. There are 'n' such subsets. And each of them has their A.M. as integer. 3. Now let's consider the subsets with size >= 2 which have an integer A.M. Let G be the set of all such subsets. Let's consider a function 'f' defined for subsets of size >= 2. f(S) = S - {k} where k is the A.M. of S and k is present in S. f(S) = S + {k} where k is the A.M. of S and k is not present in S. For e.g. S = {1,3,8}, k = (1+3+8)/3 = 4 4 is not there in S. f(S) = {1,3,4,8} S = {1,2,3}, k = (1+2+3)/2 = 3 3 is there in S. f(S) = {1,2} Note 1: S and f(S) have the same A.M. Why? Let S = {a1,a2...,ak} AM = sigma(a_i)/k If you remove AM, the ne...
Post a Comment
Read more

practice problems

Q1. Find integer solutions for x^2 + y^2 = 2025 S1. Mod 9 of a square gives 0,1,4,7 Here RHS is 0. For LHS to be 0, both have to give mod 0. => x = 3a, y = 3b => a^2 + b^2 = 225 Again mod 9 is 0 a = 3c, b = 3d c^2 + d^2 = 25 (c,d) = (0,+-5) (-+5,0) (-+3,-+4) (-+4,-+3) Total solutions = 2 + 2 + 4 + 4 = 12 To find actual solutions multiply c,d with 9.
Post a Comment
Read more