Square Addible

Let an integer n n be square addible by integer k k if there exists an integer x x such that

k n + 2014 x 2 k\mid n+2014x^2

Find the number of positive integers n n less than or equal to 2014 2014 that are square addible by 7 and square addible by 11, but not square addible by 13.


The answer is 292.

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

Daniel Liu
May 23, 2014

Let't's first find what numbers are square addible by 7 7 , then move on to 11 11 , and finally move on to 13 13 .

We have that 7 n + 2014 x 2 7\mid n+2014x^2 This can also be represented as n + 2014 x 2 n + 5 x 2 0 ( m o d 7 ) n+2014x^2\equiv n+5x^2\equiv 0\pmod{7}

The quadratic residues of 7 7 , after checking squares, are x 2 0 , 1 , 2 , 4 x^2\equiv 0,1,2,4 . Thus, n + 5 x 2 n + 5 ( 0 , 1 , 2 , 4 ) n + ( 0 , 5 , 3 , 6 ) 0 ( m o d 7 ) n+5x^2\equiv n+5(0,1,2,4)\equiv n+(0,5,3,6)\equiv 0\pmod{7}

Thus, n 0 , 2 , 4 , 1 ( m o d 7 ) n\equiv 0,2,4,1\pmod{7}

Now let's consider mod 11 11 . We have that n + 2014 x 2 n + x 2 0 ( m o d 11 ) n+2014x^2\equiv n+x^2\equiv 0\pmod{11}

The quadratic residues mod 11 11 are x 2 0 , 1 , 3 , 4 , 5 , 9 ( m o d 11 ) x^2\equiv 0,1,3,4,5,9\pmod{11} . Thus, n + x 2 n + ( 0 , 1 , 3 , 4 , 5 , 9 ) 0 ( m o d 11 ) n+x^2\equiv n+(0,1,3,4,5,9)\equiv 0\pmod{11}

Therefore n 0 , 10 , 8 , 7 , 6 , 2 ( m o d 11 ) n\equiv 0,10,8,7,6,2\pmod{11}

Finally, we consider mod 13 13 . We have n + 2014 x 2 n + 12 x 2 ≢ 0 ( m o d 13 ) n+2014x^2\equiv n+12x^2\not\equiv 0\pmod{13}

The quadratic residues mod 13 13 are x 2 0 , 1 , 3 , 4 , 9 , 10 , 12 ( m o d 13 ) x^2\equiv 0,1,3,4,9,10,12\pmod{13} . Thus, n + 12 x 2 n + 12 ( 0 , 1 , 3 , 4 , 9 , 10 , 12 ) n + ( 0 , 12 , 10 , 9 , 4 , 3 , 1 ) ≢ 0 ( m o d 13 ) n+12x^2\equiv n+12(0,1,3,4,9,10,12)\equiv n+(0,12,10,9,4,3,1)\not\equiv 0\pmod{13}

Thus, n ≢ 0 , 1 , 3 , 4 , 9 , 10 , 12 ( m o d 13 ) n\not\equiv 0,1,3,4,9,10,12 \pmod{13} so n 2 , 5 , 6 , 7 , 8 , 11 ( m o d 13 ) n\equiv 2,5,6,7,8,11\pmod {13}

Thus, we have the following set of modular equations: { n 0 , 2 , 4 , 1 ( m o d 7 ) n 0 , 10 , 8 , 7 , 6 , 2 ( m o d 11 ) n 2 , 5 , 6 , 7 , 8 , 11 ( m o d 13 ) \left\{\begin{array}{l}n\equiv 0,2,4,1\pmod{7}\\ n\equiv 0,10,8,7,6,2\pmod{11}\\ n\equiv 2,5,6,7,8,11\pmod {13}\end{array}\right.

By the Chinese Remainder Theorem, there exists exactly one solution mod 7 11 13 = 1001 \text{mod }7\cdot 11\cdot 13=1001 for each possible choice of mod 7 \text{mod }7 , mod 11 \text{mod }11 , and mod 13 \text{mod }13 . Thus, there are 4 × 6 × 6 = 144 4\times 6\times 6=144 solutions mod 1001 \text{mod }1001 .

Therefore, there are 2 × 144 = 288 2\times 144=288 solutions between 1 1 and 2002 2002 . However, we also have to check 2003 2014 2003\to 2014 to see if there are any more solutions. Taking mod 1001 1001 , we check the numbers 1 12 1\to 12 .

We find that 2 , 7 , 8 , 11 2, 7, 8, 11 are the numbers that satisfy our system of modular equations. Thus, there are 288 + 4 = 292 288+4=\boxed{292} solutions total.

Darn I did all of that but forgot 2013 :(

Nathan Ramesh - 7 years ago

Log in to reply

Man that sucks for you bro. :D

Finn Hulse - 7 years ago

Log in to reply

I included the one from 1-12 that WAS 13 addible D:<

Kaan Dokmeci - 7 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...