Such numbers always scare me!

Number Theory Level 5

The number of coprime ordered pairs for $x_0+y_0=17291729$ is $m$ ;

The number of coprime ordered pairs for $x_1+y_1=m$ is $n$ ;

The number of coprime ordered pairs for $x_2+y_2=n$ is $l$ .

Find the value of $(m+n+l) \pmod {1729}$ .

The answer is 1687.

1 solution

Mehul Chaturvedi
Jan 29, 2015

Please upvote if you like the solution

If $x+y=n$ and $x,y$ are coprime ordered pairs then the number of coprime ordered pairs of $x,y$ $=\phi n$ where $\phi$ is Euler's totient function

$\Rightarrow$ $x_0+y_0=17291729$ $\therefore$ total $(x_0,y_0)=m=\phi 17291729=12690432$

$\Rightarrow$ $x_1+y_1=12690432$ therefore total $(x_1,y_1)=n=\phi 12690432=3981312$

$\Rightarrow$ $x_2+y_2=3981312$ therefore total $(x_2,y_2)=l=\phi 3981312=1327104$

$\Rightarrow$ $\therefore m+n+l=17998848 \therefore (m+n+l) \mod 1729= 1687$

Hence our answer is $\huge{\boxed{\color{royalblue}{1687}}}$

Note: Number is very poorly chosen it took me one hour to find totient function of all the numbers

Correct @Mehul Chaturvedi

Parth Lohomi - 6 years, 4 months ago

It's relatively easy to get the totient functions once we know that $1729=7\cdot13\cdot19$ and $10001=73\cdot137$

Factorise $17291729=7\cdot13\cdot19\cdot73\cdot137$ to get: $m=\phi(17291729)=6\cdot12\cdot18\cdot72\cdot136=2^{10}\cdot3^6\cdot17$

$n=\phi(2^{10}\cdot3^6\cdot17)=2^{9}\cdot(2\cdot3^3)\cdot16=2^{14}\cdot3^5$

$l=\phi(2^{14}\cdot3^5)=2^{13}\cdot(2\cdot3^4)\cdot16=2^{14}\cdot3^4$

We then get $m+n+l=2^{10}\cdot3^4\cdot(9\cdot17+16\cdot3+16)=2^{10}\cdot3^4\cdot 217$ .

We note that this is divisible by 7, so we just find the sum modulo $13\cdot19=247$ . Finding that $2^{10}\cdot3^4\cdot 217\equiv205\pmod{247}$ (Using some shortcuts like $217\equiv\ -30\pmod{247},(2^{10}\equiv36\pmod{247}$ ), we apply CRT to get $m+n+l\equiv\boxed{1687}\pmod{1729}$

Jared Low - 6 years, 4 months ago

Such numbers always scare me!

The answer is 1687.

1 solution

0 pending reports