Science:Math Exam Resources/Courses/MATH437/December 2006/Question 02

MATH437 December 2006

Work in progress: this question page is incomplete, there might be mistakes in the material you are seeing here.

• Q1 • Q2 • Q3 • Q4 • Q5 • Q6 • Q7 • Q8 •

Other MATH437 Exams

• December 2006 • December 2011 •

[hide] Question 02
Find all values of a for which the congruence $\displaystyle x^{6}\equiv a\mod {31}$ has integer solutions.

Make sure you understand the problem fully: What is the question asking you to do? Are there specific conditions or constraints that you should take note of? How will you know if your answer is correct from your work only? Can you rephrase the question in your own words in a way that makes sense to you?

If you are stuck, check the hints below. Read the first one and consider it for a while. Does it give you a new idea on how to approach the problem? If so, try it! If after a while you are still stuck, go for the next hint.

[show] Hint 1
The general strategy for this problem will be to evaluate the value of $\displaystyle x^{6}$ at all integers between 0 and 30 inclusive.

[show] Hint 2
Notice that $\displaystyle 31=32-1=2^{5}-1$ so evaluating $\displaystyle x^{6}$ at powers of two should be fairly straight forward.

[show] Hint 3
For other values of x, try to swap between x and its negation to help with the computations. You don't need to compute a lot of values by hand before you can quickly do all 31 values.

[show] Hint 4
Compute it for some small values of primes then use this information along with hint 2 to immediately calculate this for all such values.

Checking a solution serves two purposes: helping you if, after having used all the hints, you still are stuck on the problem; or if you have solved the problem and would like to check your work.

If you are stuck on a problem: Read the solution slowly and as soon as you feel you could finish the problem on your own, hide it and work on the problem. Come back later to the solution if you are stuck or if you want to check your work.
If you want to check your work: Don't only focus on the answer, problems are mostly marked for the work you do, make sure you understand all the steps that were required to complete the problem and see if you made mistakes or forgot some aspects. Your goal is to check that your mental process was correct, not only the result.

[show] Solution
Found a typo? Is this solution unclear? Let us know here. Please rate my easiness! It's quick and helps everyone guide their studies. Clearly $\displaystyle 0^{6}\equiv 0\mod {31}$ and $\displaystyle (\pm 1)^{6}\equiv 1\mod {31}$ so throughout we suppose that both x is greater than 1 but less than 30. This leaves 28 such values left to be computed. We begin by computing at powers of two. Since $\displaystyle (\pm 2)^{6}\equiv (\pm 1)^{6}\cdot 2^{5}\cdot 2\equiv 2\mod {31}$ we see that a equals 2 is an admissable value. Further, we immediately get that $\displaystyle (2^{b})^{6}\equiv (2^{6})^{b}\equiv 2^{b}\mod {31}$ and so for b ranging from 1 to 4 we see that a can take on the values 2,4,8 or 16. This covers the x values $\displaystyle x=\pm 2,\pm 4,\pm 8,\pm 16$ . Next for x equals $\pm 3$ , notice that $\displaystyle (\pm 3)^{6}\equiv (3^{3})^{2}\equiv (27)^{2}\equiv (-4)^{2}\equiv 16\mod {31}$ which gives us an already chosen a value. Using these facts, we can clearly see that Further at x equals $\pm 5$ , $\displaystyle (\pm 5)^{6}\equiv (5^{2})^{3}\equiv (-6)^{3}\equiv -6\cdot 36\equiv -6\cdot 5\equiv 1$ and this value was also an already chosen a value. I claim that these values are enough to show that all admissable values of a have already been found. To see this, notice for example that $\displaystyle (\pm 6)^{6}\equiv 3^{6}\cdot 2^{6}\mod {31}$ and the right hand side was already shown to be a power of 2. Similarly $\displaystyle (\pm 7)^{6}\equiv (\pm 1)^{6}(7)^{6}\equiv (-7)^{6}\equiv (24)^{6}\equiv (2^{3})^{6}\cdot 3^{6}\mod {31}$ is also a power of 2. Crunching through the remaining cases, we have $\displaystyle (\pm 9)^{6}\equiv (3^{6})^{2}\mod {31}$ $\displaystyle (\pm 10)^{6}\equiv 2^{6}\cdot 5^{6}\mod {31}$ $\displaystyle (\pm 11)^{6}\equiv (\pm 1)^{6}(11)^{6}\equiv (-11)^{6}\equiv 20^{6}\mod {31}$ $\displaystyle (\pm 12)^{6}\equiv 4^{6}\cdot 3^{6}\mod {31}$ $\displaystyle (\pm 13)^{6}\equiv (\pm 1)^{6}(13)^{6}\equiv (-13)^{6}\equiv (18)^{6}\equiv \equiv 2^{6}\cdot 9^{6}\mod {31}$ $\displaystyle (\pm 14)^{6}\equiv 2^{6}\cdot 7^{6}\mod {31}$ and in all these cases, we have already shown the right hand side to be a power of 2. Thus the admissable values for a are given by $\displaystyle a\in \{0,1,2,4,8,16\}$ .