Eight digit bank identification number and other problems of elementary number theory

Question 1:

Consider the eight-digit bank identification number a_{1}a_{2}\ldots a_{8}, which is followed by a ninth check digit a_{9} chosen to satisfy the congruence

a_{9} \equiv 7a_{1} + 3a_{2} + 9a_{3} + 7a_{4} + 3a_{5} + 9a_{6} + 7a_{7} + 3a_{8} {\pmod {10}}

(a) Obtain the check digits that should be appended to the two numbers 55382006 and 81372439.

(b) The bank identification number 237a_{4}18538 has an illegitimate fourth digit. Determine the value of the obscured digit.

Question 2:

(a) Find an integer having the remainders 1,2,5,5 when divided by 2, 3, 6, 12 respectively (Yih-hing, died 717)

(b) Find an integer having the remainders 2,3,4,5 when divided by 3,4,5,6 respectively (Bhaskara, born 1114)

(c) Find an integer having remainders 3,11,15 when divided by 10, 13, 17, respectively (Regiomontanus, 1436-1476)

Question 3:

Question 3:

Let t_{n} denote the nth triangular number. For which values of n does t_{n} divide t_{1}^{2} + t_{2}^{2} + \ldots + t_{n}^{2}

Hint: Because t_{1}^{2}+t_{2}^{2}+ \ldots + t_{n}^{2} = t_{n}(3n^{3}+12n^{2}+13n+2)/30, it suffices to determine those n satisfying 3n^{3}+12n^{2}+13n+2 \equiv 0 {\pmod {2.3.5}}

Question 4:

Find the solutions of the system of congruences:

3x + 4y \equiv 5 {\pmod {13}}
2x + 5y \equiv 7 {\pmod {13}}

Question 5:

Obtain the two incongruent solutions modulo 210 of the system

2x \equiv 3 {\pmod 5}
4x \equiv 2 {\pmod 6}
3x \equiv 2 {\pmod 7}

Question 6:

Use Fermat’s Little Theorem to verify that 17 divides 11^{104}+1

Question 7:

(a) If gcd(a,35)=1, show that a^{12} \equiv {\pmod {35}}. Hint: From Fermat’s Little Theorem, a^{6} \equiv 1 {\pmod 7} and a^{4} \equiv 1 {\pmod 5}

(b) If gcd(a,42) =1, show that 168=3.7.8 divides a^{6}-1
(c) If gcd(a,133)=gcd(b,133)=1, show that 133| a^{18} - b^{18}

Question 8:

Show that 561|2^{561}-1 and 561|3^{561}-3. Do there exist infinitely many composite numbers n with the property that n|2^{n}-2 and n|3^{n}-3?

Question 9:

Prove that any integer of the form n = (6k+1)(12k+1)(18k+1) is an absolute pseudoprime if all three factors are prime; hence, 1729=7.13.19 is an absolute pseudoprime.

Question 10:

Prove that the quadratic congruence x^{2}+1 \equiv 0 {\pmod p}, where p is an odd prime, has a solution if and only if p \equiv {pmod 4}.

Note: By quadratic congruence is meant a congruence of the form ax^{2}+bx+c \equiv 0 {\pmod n} with a \equiv 0 {\pmod n}. This is the content of the above proof.

More later,
Nalin Pithwa.

Pre RMO algebra : some tough problems

Question 1:

Find the cube root of x^{3} -12x^{2} + 54x -112 + \frac{108}{x} - \frac{48}{x^{2}} + \frac{8}{x^{3}}

Question 2:

Find the square root of \frac{x}{y} + \frac{y}{x} +3 - 2\sqrt{\frac{x}{y}} -2\sqrt{\frac{y}{x}}

Question 3:

Simplify (a):

(\frac{x}{x-1} - \frac{1}{x+1}). \frac{x^{3}-1}{x^{6}+1}.\frac{(x-1)^{2}(x+1)^{2}+x^{2}}{x^{4}+x^{2}+1}

Simplify (b):
\{ \frac{a^{4}-y^{4}}{a^{2}-2ay+y^{2}} \div \frac{a^{2}+ay}{a-y} \} \times \{ \frac{a^{5}-a^{3}y^{2}}{a^{3}+y^{3}} \div \frac{a^{4}-2a^{3}y+a^{2}y^{2}}{a^{2}-ay+y^{2}}\}

Question 4:

Solve : \frac{3x}{11} + \frac{25}{x+4} = \frac{1}{3} (x+5)

Question 5:

Solve the following simultaneous equations:

2x^{2}-3y^{2}=23 and 2xy - 3y^{2}=3

Question 6:

Simplify (a):

\frac{1- \frac{a^{2}}{(x+a)^{2}}}{(x+a)(x-a)} \div \frac{x(x+2a)}{(x^{2}-a^{2})(x+a)^{2}}

Simplify (b):

\frac{6x^{2}y^{2}}{m+n} \div \{\frac{3(m-n)x}{7(r+s)} \div \{ \frac{4(r-s)}{21xy^{2}} \div \frac{(r^{2}-s^{2})}{4(m^{2}-n^{2})}\} \}

Question 7:

Find the HCF and LCM of the following algebraic expressions:

20x^{4}+x^{2}-1 and 25x^{4}+5x^{3} - x - 1 and 25x^{4} -10x^{2} +1

Question 8:

Simplify the following using two different approaches:

\frac{5}{6- \frac{5}{6- \frac{5}{6-x}}} = x

Question 9:

Solve the following simultaneous equations:

Slatex x^{2}y^{2} + 192 = 28xy$ and x+y=8

Question 10:

If a, b, c are in HP, then show that

(\frac{3}{a} + \frac{3}{b} - \frac{2}{c})(\frac{3}{c} + \frac{3}{b} - \frac{2}{a})+ \frac{9}{b^{2}}=\frac{25}{ac}

Question 11:

if a+b+c+d=2s, prove that

4(ab+cd)^{2} - (a^{2}+b^{2}-c^{2}-d^{2})^{2}= 16(s-a)(s-b)(s-c)(s-d)

Question 12:

Determine the ratio x:y:z if we know that

\frac{x+z}{y} = \frac{z}{x} = \frac{x}{z-y}

More later,
Nalin Pithwa

Those interested in such mathematical olympiads should refer to:

https://olympiads.hbcse.tifr.res.in

(I am a tutor for such mathematical olympiads).

Pre RMO more algebra problems for practice

Question I:

I rode one third of a journey at 10kmph, one third more at 9, and the rest at 8 kmph; if I had ridden half the journey at 10kmph, and the other half at 8 kmph, I should have been half a minute longer on the way: what distance did I ride?

Question 2:

The express train leaves Bristol at 3pm and reaches London at 6pm; the ordinary train leaves London at 1:30pm and arrives at Bristol at 6pm. If both trains travel uniformly, find the time when they will meet.

Question 3:

Solve (a) 0.\dot{6}x + 0.75x-0.1\dot{6} = x - 0.58\dot{3}x+5

Solve (b) \frac{37}{x^{2}-5x+6} + \frac{4}{x-2} = \frac{7}{3-x}

Question 4:

Simplify: (1+x)^{2} \div \{ 1 + \frac{x}{1-x+ \frac{x}{1+x+x^{2}}}\}

Question 5:

Find the square root of \frac{4a^{2}-12ab-6bc+4ac+9b^{2}+c^{2}}{4a^{2}+9c^{2}-12ac}

Question 6:

Find the square root of 4a^{4}+9(a^{2}+\frac{1}{a^{2}})+12a(a^{2}+1)+18

Question 7:

Solve the following system of equations:

\frac{1}{3}(x+y)+2z=21

3x - \frac{1}{2}(y+z) = 65

x + \frac{1}{2}(x+y-z) = 38

Question 8:

A number consists of three digits, the right hand one being zero. If the left hand and middle digits be interchanged the number is diminished by 180; if the left hand digit be halved and the other two digits are interchanged, the number is diminished by 336; find the number.

Question 9:

Add together the following fractions:

\frac{2}{x^{2}+xy+y^{2}}, \frac{-4x}{x^{3}-y^{3}}, \frac{x^{2}}{y^{2}(x-y)^{2}}, and \frac{-x^{2}}{x^{3}y-y^{4}}

Question 10:

Simplify:

\frac{a^{3}+b^{3}}{a^{4}-b^{4}} - \frac{a+b}{a^{2}-b^{2}} -\frac{1}{2} \{ \frac{a-b}{a^{2}+b^{2}} - \frac{1}{a-b} \}

More later,
Nalin Pithwa

Pre RMO Algebra problems for practice

Question 1:

Find the square root of 49x^{4}+\frac{1051x^{2}}{25} - \frac{14x^{3}}{5} - \frac{6x}{5} + 9

Question 2:

The surface area of a circular cone is given by A= {\pi}r^{2}+{\pi}rs, where s cm is the slant height, r cm is the radius of the base and \pi is \frac{22}{7}. Find the radius of the base if a cone of surface area 93.5 square cm has a slant height of 5 cm.

Question 3:

Solve:

\frac{a+x}{a^{2}+ax+x^{2}} +\frac{a-x}{a^{2}-ax+ x^{2}} = \frac{3a}{x(a^{4}+a^{2}x^{2}+x^{4})}

Question 4:

Subtract \frac{x+3}{x^{2}+x-12} + \frac{x+4}{x^{2}-x-12} and divide the difference by 1 + \frac{2(x^{2}-12)}{x^{2}+7x+12}

Question 5:

Solve the following for the unknown x:

\frac{x}{2(x+3)} - \frac{53}{24} = \frac{x^{2}}{x^{2}-9} - \frac{8x-1}{4(x-3)}

Question 6:

Find the square root of the following:

a^{6}+ \frac{1}{a^{6}} -6(a^{4}+\frac{1}{a^{4}}) +12(a^{2}+\frac{1}{a^{2}})-20; also, cube the result.

More later,
Nalin Pithwa.

How to find the number of proper divisors of an integer and other cute related questions

Question 1:

Find the number of proper divisors of 441000. (A proper divisor of a positive integer n is any divisor other than 1 and n):

Solution 1:

Any integer can be uniquely expressed as the product of powers of prime numbers (Fundamental theorem of arithmetic); thus, 441000 = (2^{3})(3^{2})(5^{3})(7^{2}). Any divisor, proper or improper, of the given number must be of the form (2^{a})(3^{b})(5^{c})(7^{d}) where 0 \leq a \leq 3, 0 \leq b \leq 2, 0 \leq c \leq 3, and 0 \leq d \leq 2. In this paradigm, the exponent a can be chosen in 4 ways, b in 3 ways, c in 4 ways, d in 3 ways. So, by the product rule, the total number of proper divisors will be (4)(3)(4)(3)-2=142.

Question 2:

Count the proper divisors of an integer N whose prime factorization is: N=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} p_{3}^{\alpha_{3}}\ldots p_{k}^{\alpha_{k}}

Solution 2:

By using the same reasoning as in previous question, the number of proper divisors of N is (\alpha_{1}+1)(\alpha_{2}+1)(\alpha_{3}+1)\ldots (\alpha_{k}+1)-2, where we deduct 2 because choosing all the factors means selecting the given number itself, and choosing none of the factors means selecting the trivial divisor 1.

Question 3:

Find the number of ways of factoring 441000 into 2 factors, m and n, such that m>1, n>1, and the GCD of m and n is 1.

Solution 3:

Consider the set A = {2^{3}, 3^{2}, 5^{3}, 7^{2}} associated with the prime factorization of 441000. It is clear that each element of A must appear in the prime factorization of m or in the prime factorization of n, but not in both. Moreover, the 2 prime factorizations must be composed exclusively of elements of A. It follows that the number of relatively prime pairs m, n is equal to the number of ways of partitioning A into 2 unordered nonempty, subsets (unordered as mn and nm mean the same factorization; recall the fundamental theorem of arithmetic).

The possible unordered partitions are the following:

A = \{ 2^{3}\} + \{ 3^{2}, 5^{3}, 7^{2}\} = \{3^{2}\}+\{ 2^{3}, 5^{3}, 7^{2}\} = \{ 5^{3}\} + \{ 2^{3}, 3^{2}, 7^{2}\} = \{ 7^{2}\}+\{ 2^{3}, 3^{2}, 5^{3}\},

and A = \{ 2^{3}, 3^{2}\} + \{ 5^{3}, 7^{2}\}=\{ 2^{3}, 5^{3}\} + \{3^{2}, 7^{2} \} = \{ 2^{3}, 7^{2}\} + \{ 3^{2}, 5^{3}\}

Hence, the required answer is 4+3=2^{4-1}+1=7.

Question 4:

Generalize the above problem by showing that any integer has 2^{k-1}-1 factorizations into relatively prime pairs m, n (m>1, n>1).

Solution 4:

Proof by mathematical induction on k:

For k=1, the result holds trivially.

For k=2, we must prove that a set of k distinct elements, Z = \{ a_{1}, a_{2}, a_{3}, \ldots, a_{k-1}, a_{k}\} has 2^{k-1}-1 sets. Now, one partition of Z is

Z = \{ a_{k}\} \bigcup \{ a_{1}, a_{2}, a_{3}, \ldots, a_{k-1}\} \equiv \{ a_{k}\} \bigcup W

All the remaining partitions may be obtained by first partitioning W into two parts — which, by the induction hypothesis, can be done in 2^{k-2}-1 ways — and then, including a_{k} in one part or other — which can be done in 2 ways. By the product rule, the number of partitions of Z is therefore

1 + (2^{k-2})(2)=2^{k-1}-1. QED.

Remarks: Question 1 can be done by simply enumerating or breaking it into cases. But, the last generalized problem is a bit difficult without the refined concepts of set theory, as illustrated; and of course, the judicious use of mathematical induction is required in the generalized case. 

Cheers,

Nalin Pithwa.