Must Have All Integers

Number Theory Level 5

Given two integers m , n , m, n, a set S m , n \mathbb{S}_{m,n} consisting of integers is defined as follows:

  • m , n ∈ S m , n m, n \in \mathbb{S}_{m,n}
  • Consider an integer x ≠ m , n . x \neq m,n. Then, x ∈ S m , n x \in \mathbb{S}_{m,n} if and only if there exist two a , b ∈ S a, b \in \mathbb{S} and a k ∈ Z k \in \mathbb{Z} such that a 2 + k a b + b 2 = x . a^2+kab+b^2=x.

Find the number of positive integer pairs ( m , n ) (m,n) such that 1 ≤ m < n ≤ 5 1 \leq m < n \leq 5 and for all possibilities of S m , n , \mathbb{S}_{m,n}, S m , n = Z . \mathbb{S}_{m,n} = \mathbb{Z}.

Details and assumptions

  • The condition in the last sentence implies that S m , n \mathbb{S}_{m,n} must contain all integers.
  • a a and b b need not be distinct in the second condition.
  • This problem is adapted from ISL.


The answer is 9.

Sreejato Bhattacharya by Sreejato Bhattacharya , 22, India

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

Note that gcd ⁡ ( m , n ) ∣ m 2 + k m n + n 2 ∀ k ∈ Z , \gcd (m, n) \mid m^2 + kmn + n^2 \quad \forall \ k \in \mathbb{Z}, from which we trivially deduce that gcd ⁡ ( m , n ) \gcd (m,n) must be a divisor of all elements of S m , n . \mathbb{S}_{m,n}. If gcd ⁡ ( m , n ) > 1 , \gcd (m,n) > 1, no number which isn't a multiple of gcd ⁡ ( m , n ) \gcd (m,n) can be in S m , n , \mathbb{S}_{m,n}, so S m , n ⊂ Z . \mathbb{S}_{m,n} \subset \mathbb{Z}.

We shall show that if gcd ⁡ ( m , n ) = 1 , \gcd (m,n) = 1, S m , n = Z . \mathbb{S}_{m,n} = \mathbb{Z}.

Claim 1: x ∈ S m , n ⟹ j x 2 ∈ S m , n ∀ j ∈ Z x \in \mathbb{S}_{m,n} \implies jx^2 \in \mathbb{S}_{m,n} \quad \forall \ j \in \mathbb{Z}

Proof: Setting a = x , b = x , k = j − 2 , a= x, b= x, k= j-2, x 2 + x 2 + ( j − 2 ) x 2 ∈ S m , n ⟹ j x 2 ∈ S m , n . x^2 + x^2 + (j-2)x^2 \in \mathbb{S}_{m,n} \implies jx^2 \in \mathbb{S}_{m,n}.

Claim 2: a , b ∈ S m , n ⟹ ( a − b ) 2 ∈ S m , n a, b \in \mathbb{S}_{m,n} \implies (a-b)^2 \in \mathbb{S}_{m,n}

Proof: Setting k = − 2 , k= -2, a 2 − 2 a b + b 2 ∈ S m , n ⟹ ( a − b ) 2 ∈ S m , n . a^2 - 2ab + b^2 \in \mathbb{S}_{m,n} \implies (a-b)^2 \in \mathbb{S}_{m,n}.

Since gcd ⁡ ( m , n ) = 1 , \gcd (m,n)=1, by Bezout's lemma there exist integers a , b a, b such that a m 2 − b n 2 = 1. am^2 - bn^2= 1. By claim 1, a m 2 , b n 2 ∈ S m , n , am^2, bn^2 \in \mathbb{S}_{m,n}, and by claim 2, ( a m 2 − b n 2 ) 2 = 1 ∈ S m , n . (am^2 - bn^2)^2 = 1 \in \mathbb{S}_{m,n}. Again, by claim 1, j ⋅ 1 2 ∈ S m , n ∀ j ∈ Z ⟹ S m , n = Z . j \cdot 1^2 \in \mathbb{S}_{m,n} \quad \forall \ j \in \mathbb{Z} \implies \mathbb{S}_{m,n} = \mathbb{Z}.

So, the answer is the number of pairs of positive integers ( m , n ) (m, n) such that 1 ≤ m < n ≤ 5 1 \leq m < n \leq 5 and gcd ⁡ ( m , n ) = 1 , \gcd (m,n) = 1, which is simply ∑ k = 2 5 φ ( k ) = 9 . \displaystyle \sum_{k=2}^{5} \varphi (k) = \boxed{9}.

4 Helpful 0 Interesting 0 Brilliant 0 Confused

Nice problem.

Peter Byers - 7 years, 1 month ago

Log in to reply

P.S. It occurs to me, notwithstanding the "if and only if" you already have in there, that you ought to say that S m , n \mathbb{S}_{m,n} is the smallest set that satisfies those 2 conditions. Otherwise, the 2 conditions do not uniquely determine a set. (This is a technical point -- presumably the reader will know what you mean anyhow.)

Peter Byers - 7 years, 1 month ago

Log in to reply

Yeah, I agree. I've changed the problem statement, so all possible sets S m , n \mathbb{S}_{m,n} must be equal to Z . \mathbb{Z}.

Sreejato Bhattacharya - 7 years, 1 month ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...