Let an integer be square addible by integer if there exists an integer such that
Find the number of positive integers less than or equal to that are square addible by 7 and square addible by 11, but not square addible by 13.
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.
Let't's first find what numbers are square addible by 7 , then move on to 1 1 , and finally move on to 1 3 .
We have that 7 ∣ n + 2 0 1 4 x 2 This can also be represented as n + 2 0 1 4 x 2 ≡ n + 5 x 2 ≡ 0 ( m o d 7 )
The quadratic residues of 7 , after checking squares, are x 2 ≡ 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 )
Thus, n ≡ 0 , 2 , 4 , 1 ( m o d 7 )
Now let's consider mod 1 1 . We have that n + 2 0 1 4 x 2 ≡ n + x 2 ≡ 0 ( m o d 1 1 )
The quadratic residues mod 1 1 are x 2 ≡ 0 , 1 , 3 , 4 , 5 , 9 ( m o d 1 1 ) . Thus, n + x 2 ≡ n + ( 0 , 1 , 3 , 4 , 5 , 9 ) ≡ 0 ( m o d 1 1 )
Therefore n ≡ 0 , 1 0 , 8 , 7 , 6 , 2 ( m o d 1 1 )
Finally, we consider mod 1 3 . We have n + 2 0 1 4 x 2 ≡ n + 1 2 x 2 ≡ 0 ( m o d 1 3 )
The quadratic residues mod 1 3 are x 2 ≡ 0 , 1 , 3 , 4 , 9 , 1 0 , 1 2 ( m o d 1 3 ) . Thus, n + 1 2 x 2 ≡ n + 1 2 ( 0 , 1 , 3 , 4 , 9 , 1 0 , 1 2 ) ≡ n + ( 0 , 1 2 , 1 0 , 9 , 4 , 3 , 1 ) ≡ 0 ( m o d 1 3 )
Thus, n ≡ 0 , 1 , 3 , 4 , 9 , 1 0 , 1 2 ( m o d 1 3 ) so n ≡ 2 , 5 , 6 , 7 , 8 , 1 1 ( m o d 1 3 )
Thus, we have the following set of modular equations: ⎩ ⎨ ⎧ n ≡ 0 , 2 , 4 , 1 ( m o d 7 ) n ≡ 0 , 1 0 , 8 , 7 , 6 , 2 ( m o d 1 1 ) n ≡ 2 , 5 , 6 , 7 , 8 , 1 1 ( m o d 1 3 )
By the Chinese Remainder Theorem, there exists exactly one solution mod 7 ⋅ 1 1 ⋅ 1 3 = 1 0 0 1 for each possible choice of mod 7 , mod 1 1 , and mod 1 3 . Thus, there are 4 × 6 × 6 = 1 4 4 solutions mod 1 0 0 1 .
Therefore, there are 2 × 1 4 4 = 2 8 8 solutions between 1 and 2 0 0 2 . However, we also have to check 2 0 0 3 → 2 0 1 4 to see if there are any more solutions. Taking mod 1 0 0 1 , we check the numbers 1 → 1 2 .
We find that 2 , 7 , 8 , 1 1 are the numbers that satisfy our system of modular equations. Thus, there are 2 8 8 + 4 = 2 9 2 solutions total.