In the cut "as" from the songs in the key of Life, Stevie Wonder mentions the equation 8*8*8*8=4. Find all integers n for which this statement is true, modulo n.
The answer in the back of the book reads "the statement is true for any divisor of 8^4 - 4=4091. I'm just confused....it doesn't make sense to me. The question says "find all integers"
Any help would be greatly appreciated!
The answer in the back of the book reads "the statement is true for any divisor of 8^4 - 4=4091. I'm just confused....it doesn't make sense to me. The question says "find all integers"
Any help would be greatly appreciated!
-
In modulo arithmetic, congruence (not equality) is based on the remainder, when you divide a number by the base of the modulus.
For example, in modulo 10, you would only keep the last digit, as that is the remainder, when you divide by 10
7 * 5 is congruent to 5 (modulo 10)
because 7 * 5 = 35 and 35/10 leaves a remainder of 5
-----
Normally we should begin with numbers higher than 4 as a base, as one does not have remainders higher that the base.
8 is congruent to 3 (modulo 5)
8*8 is therefore congruent to 3*3 = 9, congruent to -1
(8*8)*(8*8) is congruent to (-1)^2 = 1 (mod 5)
8 is congruent to 2 modulo 6
8*8 is congruent to 4 (mod 6), same as -2 (mod 6)
8*8*8*8 is congruent to (-2)^2 = 4 (mod 6)
So we know that there is one answer at n=6
But, of course, some will complain that we cannot really take n to be less than 8, so we have to keep on looking.
Using the method:
8^4 - 4 = 4092 (not 4091)
The reason that this method works is that 4092 is 4 less than 8*8*8*8. therefore, if we divide
8*8*8*8 by 4092, the remainder will be 4.
If we divide 8*8*8*8 by any divisor of 4092, the remainder will be congruent to 4 (if n is 4 or less, then of course, 4 itself will be congruent to a smaller number).
The prime factors of 4092 are:
2*2*3*11*31
Let's try a few, just for the fun of it:
n = 31
8*8 = 64 = 2*31 + 2 = 2 (mod 31)
8*8*8*8 = (2)^2 = 4 (mod 31)
n = 2*11 = 22
8*8 = 64 = 66 - 2 = -2 (mod 22)
8*8*8*8 = (-2)^2 = 4 (mod 22)
For example, in modulo 10, you would only keep the last digit, as that is the remainder, when you divide by 10
7 * 5 is congruent to 5 (modulo 10)
because 7 * 5 = 35 and 35/10 leaves a remainder of 5
-----
Normally we should begin with numbers higher than 4 as a base, as one does not have remainders higher that the base.
8 is congruent to 3 (modulo 5)
8*8 is therefore congruent to 3*3 = 9, congruent to -1
(8*8)*(8*8) is congruent to (-1)^2 = 1 (mod 5)
8 is congruent to 2 modulo 6
8*8 is congruent to 4 (mod 6), same as -2 (mod 6)
8*8*8*8 is congruent to (-2)^2 = 4 (mod 6)
So we know that there is one answer at n=6
But, of course, some will complain that we cannot really take n to be less than 8, so we have to keep on looking.
Using the method:
8^4 - 4 = 4092 (not 4091)
The reason that this method works is that 4092 is 4 less than 8*8*8*8. therefore, if we divide
8*8*8*8 by 4092, the remainder will be 4.
If we divide 8*8*8*8 by any divisor of 4092, the remainder will be congruent to 4 (if n is 4 or less, then of course, 4 itself will be congruent to a smaller number).
The prime factors of 4092 are:
2*2*3*11*31
Let's try a few, just for the fun of it:
n = 31
8*8 = 64 = 2*31 + 2 = 2 (mod 31)
8*8*8*8 = (2)^2 = 4 (mod 31)
n = 2*11 = 22
8*8 = 64 = 66 - 2 = -2 (mod 22)
8*8*8*8 = (-2)^2 = 4 (mod 22)