Secondary Special Camp 2011: NT P 2

For discussing Olympiad Level Number Theory problems
User avatar
Moon
Site Admin
Posts:751
Joined:Tue Nov 02, 2010 7:52 pm
Location:Dhaka, Bangladesh
Contact:
Secondary Special Camp 2011: NT P 2

Unread post by Moon » Fri Apr 22, 2011 10:36 am

Problem 2: Let $n$ be a positive integer. Prove that the number of ordered pairs $(a, b)$ of relatively prime positive divisors of $n$ is equal to the number of divisors of $n^2$.
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Secondary Special Camp 2011: NT P 2

Unread post by *Mahi* » Sat Apr 23, 2011 1:06 pm

$\text {Solution:}$
We are to show a two to one bijection between the set $P'$ of all the disordered $(a,b)$ and $D$ of divisors $d$ of $n^2$.
Now, from $(a,b)$ to $d$,
We have $ab \leq n$ as $gcd(a,b)=1$
So,$(ab)^2 \leq n^2$
Or, $ab^2 \leq n^2$
Again $ab^2|n^2$
For $(b,a)$ we have another one,$ba^2$
So, two elements of $P$ maps to an element of $D$.
So,$n(P') \leq 2n(D)$
Again ,let us consider any divisor $d$ of $n^2$
Let $d$ be $\prod _{i=1} {p_i}^{e_i}$
Now let us divide $d$ into two parts $d_1$ and $d_2$ , each having different prime factors and $d_1$ consisting of only those primes which have $e_i$ s odd and $d_2$ has $e_i$ s even.
Now we define $a$ as $\prod _{i=1} {p_x}^{m_x}$ where $d_1=\prod _{i=1} {p_x}^{a_x}$ and for every $x$,$m_x=\left \lfloor \frac {a_x} {2} \right \rfloor$
and $b$ as $\sqrt{d_2}$
Now,$a$ and $b$ are co-prime and they both divides $n$.And there is there reverse $b$ and $a$.
So $n(P') \geq 2n(D)$
And so ,$n(P') = 2n(D)$
Now,each ordered $(a,b)$ appears twice in $P'$,once in the form $(a,b)$ and again in $(b,a)$
So, if the set of ordered $(a,b)$ is $P$ then $n(P')=2n(P)$
So,$n(P) = n(D)$
Last edited by *Mahi* on Sun Apr 24, 2011 5:41 pm, edited 1 time in total.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

tarek like math
Posts:56
Joined:Fri Feb 18, 2011 11:30 pm

Re: Secondary Special Camp 2011: NT P 2

Unread post by tarek like math » Wed Apr 27, 2011 7:12 pm

please can any one explain with a example to clear ordered pair of relatively prime divisors of n ?[quote][/quote]

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Secondary Special Camp 2011: NT P 2

Unread post by *Mahi* » Thu Apr 28, 2011 5:27 pm

It is just like when you choose $n=60$, a pair can be $(4,15)$ where $4<15$ $gcd(4,15)=1$ and $4,15|60$
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

Post Reply