Question 1207684: Find all integers $n$, $0 \le n < 163$, such that $n$ is its own inverse modulo $8.$
Found 2 solutions by ikleyn, math_tutor2020:
Answer by ikleyn(52903)   (Show Source):
You can put this solution on YOUR website! .
Find all integers n, 0 < n < 163, such that n is its own inverse modulo 8.
~~~~~~~~~~~~~~~~~
n is own inverse modulo 8 means
n*n = 1 mod 8.
We consider numbers n modulo 8, so, it is enough to consider
the congruence classes from {1 mod 8} to {7 mod 8}.
n= 1: n*n = 1*1 = 1 mod 8. Hence, n= 1 works.
n= 2: n*n = 2*2 = 4 mod 8. Hence, n= 2 does not work.
n= 3: n*n = 3*3 = 1 mod 8. Hence, n= 3 works.
n= 4: n*n = 4*4 = 16 = 0 mod 8. Hence, n= 4 does not work.
n= 5: n*n = 5*5 = 1 mod 8. Hence, n= 5 works.
n= 6: n*n = 6*6 = 36 = 4 mod 8. Hence, n= 6 does not work.
n= 7: n*n = 7*7 = 49 = 1 mod 8. Hence, n= 7 works.
ANSWER. Among the congruence classes mod 8, classes 1, 3, 5 and 7 work as own inverses mod 8.
the rest of classes do not work as own inverses mod 8.
Solved.
/\/\/\/\/\/\/\/\/\/\/\/
Do we need to explain the obvious fact that every mathematical problem requires using
the relevant units of measurement?
In this problem we operate with equivalence classes (residues), these classes are from
{0 mod 8} to {7 mod 8}.
Therefore, references to numbers greater than 8 are inappropriate and only show/demonstrate
the general mathematical illiteracy of the person who compiled this problem.
Answer by math_tutor2020(3817)  (Show Source):
You can put this solution on YOUR website!
Tutor ikleyn has pointed out that n^2 = 1 (mod 8) has solutions:
n = 1, n = 3, n = 5, n = 7
The interesting thing is that the n = 1 and n = 7 cases pair up.
Notice how n = 7 is one short of 8, so we can think of it like n = -1 in mod 8.
Squaring -1 will generate +1 or simply 1.
Similarly, the n = 3 and n = 5 cases pair up together.
Notice n = 5 is three short of 8, in which we can think of it like n = -3 (mod 8). Squaring this leads to +9 = 9 = 1 (mod 8).
--------------------------------------------------------------------------
Slight tangent aside, the four classes of solutions were
n = 1, n = 3, n = 5, n = 7
Your teacher is asking you to look through the interval  to see which of those values of n work or not.
Let's focus on the n = 1 case.
This is when the numbers are of the form 8k+1, since each produces remainder 1 in mod 8.
Look at a few values of k.
n = 8k+1 = 8*0+1 = 1
n = 8k+1 = 8*1+1 = 9
n = 8k+1 = 8*2+1 = 17
n = 8k+1 = 8*3+1 = 25
Another way to generate this sequence is to start at 1, and add 8 to each term.
The question is now: when does this subsequence stop?
Let's set it equal to 163 and see what happens.
8k+1 = 163
8k = 163-1
8k = 162
k = 162/8
k = 20.25
If k = 20 then 8k+1 = 8*20+1 = 161
If k = 21 then 8k+1 = 8*21+1 = 167
Therefore the highest we can go in this congruence class is 161.
All of these values
{1, 9, 17, ..., 153, 161}
fit the n = 1 congruence class and are a subset of the overall solution space.
When dividing each of those items over 8, we'll get some quotient with remainder 1.
You will follow similar ideas for n = 3, n = 5, and n = 7.
I'll let the student determine those.
|
|
|
