## A bit o’ Number Theory

I recently took a trip to Virginia to visit the university I shall be attending for accepted students day. It was everything I was expecting. A beautiful campus, cool teachers, fantastic opportunities, a wonderful library (they even had a library dedicated solely to science. 🙂 ), etc. Anyways, while I was visiting, I took walk down to the Math department. While their, I walked in on a group of students working on their math homework. They mentioned they were stuck on number 6. So, I decided to help them out.

The problem was to prove that the set $\{12a + 25b | a, b \in Z\}$ is equivalent to the set of integers. The way to show two sets A and B are equivalent is to show that A is a subset of B and B is a subset of A. That is, if an item is in set A then it is also in set B, and if it is in set B it is also in set A.

It’s obvious that for any integral a and b, 12a + 25b, is an integer. But now we have to show that we can write any integer in the form of 12a + 25b. This becomes pretty obvious when one notes that 12(-2) + 25(1) = 1, and thus 12(-2N) + 25(N) = (12(-2) + 25)N = N. And, thus, all integers can be represented in this way.

Anyone who likes to play study number theory would have instantly seen that proof. Why?  There is a well known theorem stating that given two integers, x and y, you can write their greatest common divisor as a sum, ax + by, where a and b are integers. A proof of this can be found on wikipedia. It might, however, be a fun exercise to try and prove it yourself.

If you manage to prove it yourself, another similar problem would be to try to find what numbers can be produced when a and b are restricted to being positive or 0. Take for instance 10 and 13. You obviously can’t make the number 12, and can make 26. But can you make 98? 112? 589?. Just something to think about. 