I was studying symmetries (as an introduction to Group Theory) and found this question-
Let $p,q$ be relatively prime positive integers and let $X$ be the set of integers that cannot be written as $ap+bq$ where $a,b$ are non-negative integers. For example, if $p=3$, $q=7$, then $X=\{1,2,4,5,8,11\}$
a. Find the largest element in $X$ in terms of $p$ and $q$.
b. Find the cardinality of $X$ (hint: plot the elements of $X$ on the real line and discover a hidden symmetry. In the example given, this gives:
where the black dots represent the elements of $X$.
Now, after doing a little bit of trial and error, I guessed that the largest element in $X$ is $pq-p-q$. I can even prove that the equation
$$ap+bq=pq-p-q$$
does not have any solutions in non-negative integers. But, how can I show that this is the largest number for which no such solution exists? Also, how is this question related to symmetry (if it at all is)?
About the second part, I can neither guess a solution, nor understand the hidden symmetry in the given diagram. Please help me with this.
Edit: Just came to know that part (a) is known as Coin Problem.
Edit 2: After the actual problem is solved, I'm curious of something else. We can see in the wiki article that the coin problem has elaborate solutions only for two coins. But, why can't we have any such beautiful symmetry for $n>2$ coins?
Best Answer
Definition: For relatively prime positive $a, b \in \Bbb Z^+$, an integer $z$ is $(a, b)$-representable (or representable when $a$ and $b$ are fixed) when there exist $x, y \in \Bbb N$ such that $ax + by = z.$
Claim: Let $m, n \in \Bbb Z$ such that $m + n = ab - a - b$. Then exactly one of $m$ or $n$ is representable.
Note that the solution to the Coin Problem follows directly from the claim. Because $m = 0$ is always representable, $ab - a - b$ can never be representable. However, no negative integer can ever be representable, so every integer larger than $ab - a - b$ must be representable.
It remains, then, to prove the Claim.
Lemma: Let $a, b \in \Bbb Z^+$ be relatively prime. Then there exists a unique $x \in \Bbb Z$ such that $ax + by = z$ and $0 \leq x \lt b$ with $y \in \Bbb Z$. Also, $z$ is representable if and only if it is representable in this form.
Proof of Lemma: Existence: Choose $s, t \in \Bbb Z$ such that $as + bt = z$. Some such $s$ and $t$ exist because $a$ and $b$ are relatively prime. Then $\exists q, r \in \Bbb Z$ such that $s = qb + r$, where $0 \leq r \lt b$.
We have $z = as + bt = a(qb + r) + bt = ar + b(aq + t)$, and $r$ meets the conditions of the Lemma.
Uniqueness: Assume $z = ax + by = at + bs$, where $0 \leq x, t \lt b$. Then $a(x - t) = b(s - y)$, so $b \mid a(x - t)$. Since $(a, b)=1$, this means $b \mid (x - t)$. But $-(b - 1) \leq (x - t) \leq b - 1$, so $b \mid (x - t) \Rightarrow x = t$.
Representability: Obviously, if $z$ is representable in this form, it is representable. Assume it is representable as $ax + by$ for some $x, y \in \Bbb N$. Then if $x \geq b$, then $x=qb+x_0$ for some $q \gt 0, 0 \leq x_0 \lt b$, so $z=ax+by=a(qb+x_0)+by=ax_0+b(y+aq)$ and $y, q \geq 0 \Rightarrow y+ aq \geq 0$, so we have shown that $z$ is representable in the required form.
Proof of Claim: Using the Lemma, choose the unique $x$ and $u$ such that $0 \leq x, u \lt b, ax + by = m$, and $au + bv = n$.
Then $m + n = ab - a - b = a(x + u) + b(y + v),$ so $$ab - b(1 + y + v) = a(x + u + 1).$$ Since $b$ divides both summands on the left side, it must also divide the right side, and since $a$ and $b$ are relatively prime, we have $b \mid (x + u + 1)$. Since $1 \leq (x + u + 1) \leq 2b - 1$, we have $x + u + 1 = b$.
Thus, $ab - b(1 + y + v) = ab$, so $b(1 + y + v) = 0$, or $y + v = -1$, so exactly one of $y$ and $v$ is negative, and the other is non-negative. If $y$ is non-negative, then $m$ is representable and $n$ is not, and if $v$ is non-negative, then $n$ is representable and $m$ is not.