GRE Problems - Variants

This problem requires knowledge of modular arithmetic. If you need to review the basic concepts, look here for a short and clear summary: Modular Arithmetic, or you can do a search on Google or on YouTube. You can also read the following Background section, that is not meant to give an introduction to Modular Arithmetic, but only to provide the essential concepts needed to solve this GRE problem. If you feel you already have enough background in Modular Arithmetic, you can skip this section and go directly to the Solution below.

Background
We can summarize both the notation and most of the concepts needed for this problem in this one statement: \( x\equiv y \pmod{n}\) means that \(x-y\) is divisible by \(n\). So for example \(3\equiv 10 \pmod{7}\), and \(7\equiv-1 \pmod{8}\). And clearly \(x\equiv 0\pmod{n}\) just means that \(x\) is divisible by \(n\). A useful way to think about modular arithmetic is that we simply discard numbers that are multiples of the modulo. So \(32\equiv 2 \pmod{5}\) because \(32=2+5\times 6\), and \(-2\equiv 4 \pmod{3}\) because \(-2=4-3\times 2\). If \(x\equiv y \pmod{n}\) we say that \(x\) is congruent to \(y\) modulo \(n\). So \(32\) is congruent to \(2\) modulo \(5\), and so on.

Given a positive integer \(n\), any other integer \(x\) can only have one of \(n\) possible remainders when divided by \(n\), and that is \(0\) (if \(n\) divides \(x\) exactly), or \(1\), or \(2\), or some positive integer up to \(n-1\). Denote by \({\mathbb Z}_n\) the set \(\{0,1,2,\ldots, n-1\}\). Then we can define addition and multiplication on this set as follows: given \(x\) and \(y\) in the set \({\mathbb Z}_n\), define the sum of \(x\) and \(y\) to be the unique integer in \({\mathbb Z}_n\) that is congruent to \(x+y\) modulo \(n\), and define the multiplication of \(x\) and \(y\) to be the unique integer in the same set that is congruent to \(xy\) modulo \(n\). Addition and multiplication defined on the set \({\mathbb Z}_n\) will also be denoted by \(x+y\) and \(xy\), even though they are really different operations. So for example if we consider \(5\) and \(7\) as ordinary integers, then \(5+7=12\). But if we consider them as elements of the set \({\mathbb Z}_9\) (where there is no such thing as \(12\)), then \(5+7=3\). Similarly, \(3\times 8=24\) as ordinary integers, but \(3\times 8 =6\) in \({\mathbb Z}_9\). So to say \(3\times 8 \equiv 6 \pmod{9}\) is the same as saying \(3\times 8 = 6\) in \({\mathbb Z}_9\). The notation \(x\equiv y \pmod{n}\) is quite commonly used instead of just working with elements of \({\mathbb Z}_n\) because it allows us for example to say that \(24\) is congruent to \(6\) modulo \(9\), while this statement would have no meaning in \({\mathbb Z_9}\), because there is no such element as \(24\) in \({\mathbb Z}_9\), and each element of \({\mathbb Z}_9\) can only be congruent to itself modulo \(9\).

Once we consider \({\mathbb Z}_n\) as a set with its own addition and multiplication, we can ask the question: is it possible to find a multiplicative inverse for an element of \({\mathbb Z}_n\)? That means, given an element \(x\) of \({\mathbb Z}_n\), can we find another integer \(y\) in \({\mathbb Z}_n\) such that \(xy=1\)? This question is easily answered for the ordinary integers: the only integers that have a multiplicative inverse are \(1\) and \(-1\), because for any other integer \(x\) the equation \(xy=1\) is obviously impossible. But in \({\mathbb Z}_n\) \(xy=1\) just means that \(xy-1\) is a multiple of \(n\) (or \(xy\equiv 1 \pmod{n}\)), so it is often possible to solve it. For example, in \({\mathbb Z}_6\) \(5\times 5 =1\) (because \(25=1+4\times 6\)) and so \(5 \) is its own multiplicative inverse. But for example \(2\) has no multiplicative inverse in \({\mathbb Z}_6\), as you can easily check by trying all the possibilities.

Finding a multiplicative inverse of a number is needed when solving equations. Suppose for example we want to solve the equation \[5x=2 \hspace{2ex} \mbox{ in } {\mathbb Z}_6.\] Since \(5\) is the multiplicative inverse of itself, multiply both sides by \(5\): \begin{eqnarray*}5\times 5x &=&5\times 2\\ 1\times x &=& 4\\ x&=&4 \end{eqnarray*} where we have used the fact that \(5\times 2 = 4\) in \({\mathbb Z}_6\). But the equation \(3x=2\) is not so easily solved in \({\mathbb Z}_6\), because \(3\) has no multiplicative inverse. In fact, you can check (by trying all six elements of \({\mathbb Z}_6\) for \(x\)) that the equation has no solution.

Solution
An important fact that is often used in GRE problems is the following: If \(p\) is a prime number, then every non-zero element of \({\mathbb Z}_p\) has a multiplicative inverse. Since \(7\) is prime, to solve \(5x\equiv 4 \pmod{7}\) we just need to find the multiplicative inverse of \(5\) in \({\mathbb Z}_7\), that is, an integer \(y\) such that \(5y\equiv 1 \pmod{7}\). Since \({\mathbb Z}_7=\{ 0,1,2,3,4,5,6 \}\) has only \(7\) elements, it is not hard to try them all. Discarding \(0,1\) that clearly will not work, we find \begin{eqnarray*} 2\times 5 &=& 10 \equiv 3 \pmod{7}\\ 3\times 5 &=& 15 \equiv 1 \pmod{7}\end{eqnarray*} So the multiplicative inverse of \(5\) in \({\mathbb Z}_7\) is \(3\), and multiplying the congruence \(5x\equiv 4 \pmod{7}\) by \(3\), we find \begin{eqnarray*}3\times 5x &\equiv & 3\times 4 \pmod{7}\\ 1\times x&\equiv& 12 \pmod{7}\\ x& \equiv& 5 \pmod{7} \end{eqnarray*} In a similar way, we find the multiplicative inverse of \(6\) in \({\mathbb Z}_7\) is \(6\), because \(6\times6=36=1+35\equiv 1 \pmod{7}\). So multiplying \(6y\equiv 5 \pmod{7}\) by \(6\), we find \begin{eqnarray*} 6\times 6y&\equiv& 6\times 5 \\ 1\times y &\equiv& 30 \\ y&\equiv & 2 \pmod{7}.\end{eqnarray*} We have found that \(x\equiv 5\) and \(y\equiv 2 \pmod{7}\). To say that \(x+2y+a\) is divisible by \(7\) is the same thing as saying that \(x+2y+a \equiv 0 \pmod{7}\). In other words, we need to solve this congruence for \(a\). We find: \begin{eqnarray*}x+2y+a&\equiv & 0\\ 5+2(2)+a &\equiv & 0 \\ 9+a &\equiv & 0 \\ 2+a&\equiv & 0 \\ a&\equiv & -2 \equiv 5 \pmod{7}.\end{eqnarray*} So \(a=5\) (or any other integer that is congruent to \(5\) modulo \(7\)) will work.