It's not as easy as similar ones!

n = d 6 2 + d 7 2 1 \large n=d_6^2+d_7^2-1 Find sum of all positive integers n n that satisfy equation above, where 1 = d 1 < d 2 < d 3 < < d k = n 1=d_1<d_2<d_3<\cdots<d_k=n are divisors of n n .


The answer is 2128.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Kazem Sepehrinia
Jul 23, 2015

From the equality n = d 6 2 + d 7 2 1 n = d_6^2 +d_7^2 -1 we see that d 6 d_6 and d 7 d_7 are relatively prime and d 7 d 6 2 1 = ( d 6 1 ) ( d 6 + 1 ) d_7 | d_6^2 -1 = (d_6-1)(d_6+1) , d 6 d 7 2 1 = ( d 7 1 ) ( d 7 + 1 ) d_6 | d_7^2 -1 = (d_7-1)(d_7+1) . Suppose that d 6 = a b d_6 = ab , d 7 = c d d_7 = cd with 1 < a < b 1 < a < b , 1 < c < d 1 < c < d . Then n n has 7 7 divisors smaller than d 7 d_7 , namely 1 , a , b , c , d , a b , a c 1,a,b, c,d,ab,ac , which is impossible. Hence, one of the two numbers d 6 d_6 and d 7 d_7 is either a prime p p or the square p 2 p^2 of a prime p 2 p\neq 2 .

Let it be d i d_i , { i , j } = { 6 , 7 } \left\{i, j\right\} = \left\{6, 7\right\} ; then d i ( d j 1 ) ( d j + 1 ) d_i | (d_j -1) (d_j +1) implies that d j d i ± 1 d_j\stackrel{d_i}{\equiv}\pm1 , and consequently ( d i 2 1 ) / d j d i ± 1 (d_i^2 -1)/dj \stackrel{d_i}{\equiv}\pm1 as well. But either d j d_j or ( d i 2 1 ) / d j (d_i^2 -1)/dj is less than d i d_i , and therefore equals d i 1 d_i-1 or equals 1 1 . The only nontrivial possibilities are ( d i 2 1 ) / d j = 1 (d_i^2 -1)/dj=1 and d j = d i ± 1 d_j = d_i \pm1 . In the first case we get d i < d j d_i < d_j ; hence d 7 = d 6 2 1 = ( d 6 1 ) ( d 6 + 1 ) d_7 =d_6^2 -1 = (d_6-1)(d_6+1) ; hence d 6 + 1 d_6+1 is a divisor of n n that is between d 6 d_6 and d 7 d_7 . This is impossible. We thus conclude that d 7 = d 6 + 1 d_7 = d_6 +1 . Setting d 6 = x d_6 = x , d 7 = x + 1 d_7 = x+1 we obtain that n = x 2 + ( x + 1 ) 2 1 = 2 x ( x + 1 ) n = x^2+(x+1)^2-1 = 2x(x+1) is even.

( i ) (i) Assume that one of x x , x + 1 x+1 is a prime p p . The other one has at most 6 6 divisors and hence must be of the form 2 3 , 2 4 , 2 5 , 2 q , 2 q 2 , 4 q 2^3, 2^4, 2^5, 2q, 2q^2, 4q , where q q is an odd prime. The numbers 2 3 2^3 and 2 4 2^4 are easily eliminated, while 2 5 2^5 yields the solution x = 31 x = 31 , x + 1 = 32 x+1 = 32 , n = 1984 n = 1984 . Also, 2 q 2q is eliminated because n = 4 p q n = 4pq then has only 4 4 divisors less than x x ; 2 q 2 2q^2 is eliminated because n = 4 p q 2 n=4pq^2 has at least 6 6 divisors less than x x ; 4 q 4q is also eliminated because n = 8 p q n= 8pq has 6 6 divisors less than x x .

( i i ) (ii) Assume that one of x x , x + 1 x+1 is p 2 p^2 . The other one has at most 5 5 divisors ( p p excluded), and hence is of the form 2 3 , 2 4 , 2 q 2^3, 2^4, 2q , where q q is an odd prime. The number 2 3 2^3 yields the solution x = 8 x = 8 , x + 1 = 9 x+1 = 9 , n = 144 n = 144 , while 2 4 2^4 is easily eliminated. Also, the number 2 q 2q is eliminated because n = 4 p 2 q n = 4p^2q has 6 6 divisors less than x x .

Thus there are two solutions in total: 144 144 and 1984 1984 .

What does the di and dj over the corresponding sign imply? After the di|(dj^2 - 1) step?

Satyen Dhamankar - 5 years, 10 months ago

Log in to reply

For a positive integer n n , two integers a a and b b are said to be congruent modulo n n , written: a b ( mod n ) a\equiv b \ \ (\text{mod} \ \ n) or equivalently a n b a\stackrel{n}{\equiv}b

Kazem Sepehrinia - 5 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...