|
This Lesson (Solving problems on modular arithmetic) was created by by ikleyn(53751)
  About ikleyn: Solving problems on modular arithmeticProblem 1Find the number of solutions to this system of three modular equationsN = {2 mod 5}, N = {2 mod 6}, N = {2 mod 7}. Solution
Consider integer number N-2.
It satisfies to these three modular equations
N-2 = {0 mod 5},
N-2 = {0 mod 6},
N-2 = {0 mod 7}.
It means that N-2 is a multiple of 5, 6 and 7, at the same time.
The integer numbers N-2 in the interval [-2,998] divisible by 5, 6 and 7
at the same time are those multiple of 210, i.e. 0, 210, 420, 630, 840.
Hence, the solutions N under the problem's question are the numbers 2, 212, 422, 632, 842.
In all, there are 5 solutions. ANSWER
Problem 2Let x and y be integers. If x and y satisfy 41x + 5y = 31,then find the residue of x modulo 5. Solution
You are given this equation
41x + 5y = 31, (1)
where x and y are integers. Hence
41x = 31 - 5y. (2)
They want you find residue {x mod 5} from modular equation (2).
It means that you consider equation (2) as an equivalence by modulo 5.
If so, you may forget about the term -5y, because it is 0 (zero) by the modulo 5.
So, your task is to find the residue {x mod 5} from this modular equation
41x = 31 mod 5,
which is equivalent to
41x = 1 mod 5. (3)
The set of possible solutions is x = {0 mod 5}, {1 mod 5}, {2 mod 5}, {3 mod 5} and {4 mod 5}.
x = {0 mod 5} turns (3) into 41*0 = 1 mod 5, which is obviously wrong.
x = {1 mod 5} turns (3) into 41*1 = 1 mod 5, which is obviously correct modular equation ( since 41 mod 5 = 1 mod 5).
x = {2 mod 5} turns (3) into 41*2 = 1 mod 5, which is obviously wrong.
x = {3 mod 5} turns (3) into 41*3 = 1 mod 5, which is obviously wrong.
x = {4 mod 5} turns (3) into 41*4 = 1 mod 5, which is obviously wrong.
Thus of five possible solutions only one is valid: x = {1 mod 5}. ANSWER
So, in this problem, you can easily find the answer by the brute force method.
The problem can be solved using more refined methods, but this reasoning is the number 1, which you should know and understand as a basic method to start thinking. Problem 3What is the inverse of 9 modulo 10?Solution
Inverse of 9 modulo 10 is an integer number 0 <= n <= 9 such that the product
n*9 is equal to 1 modulo 10.
As soon as you pronounce these words mentally (as the definition), the answer just should be in your mind:
+-----------------------------------------------------------+
| the inverse of 9 modulo 10 is the number 9 modulo 10. |
+-----------------------------------------------------------+
Indeed, 9*9 = 81, which is equal to 1 modulo 10.
ANSWER. The inverse of 9 modulo 10 is the number 9 modulo 10.
Problem 4Find all integers n between 0 and 7 such that n is its own inverse modulo 8.Solution
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.
Problem 5Let m and n be non-negative integers. If m = 6n + 2, thenwhat integer between 0 and m is the inverse of 2 modulo m? Solution
Notice that m = 6n+2 is an even integer number, for any integer number n.
Let's assume that an integer x between 0 and m is the inverse of 2 modulo m.
It means that 2*x = 1 mod m, which is the same as to say that
2x - 1 is a multiple of m : 2x - 1 = k*m.
But 2x is an even number, and k*m is an even number, since "m" is even.
Therefore, this equality 2x - 1 = km is not possible with integer x and "k".
Hence, there is NO any integer between 0 and m which is inverse of 2 modulo m.
ANSWER. There is NO any integer between 0 and m which is inverse of 2 modulo m.
What I proved above, in terms of abstract algebra, is THIS general statement: In the ring of integers modulo m, Z/m, where " m " is an even number, the class {2 mod m} is NOT an invertible element. In opposite, in such a ring, the class {2 mod m} is a divisor of zero; and it is well known fact of abstract algebra that in a ring a divisor of zero can not be invertible. Problem 6Find all integersSolution
(a) For our solution, the important fact is that 163 is a prime number.
Integer x is an inverse to integer n modulo 163 if and only if
nx = 1 mod 163 by the definition.
According to it, integer n is its own inverse modulo 163 if and only if
n^2 = 1 modulo 163.
One solution is trivial: it is n = 1 mod 163, or simply n= 1.
It is easy to find another (non-trivial) solution n. Take n = -1 mod 163; then n^2 = (-1)*(-1) = 1 mod 163.
So, the class n = -1 mod 163 is the other possible solution.
If we want n in the interval 0 <= n < 163, we should take n = 162, which is 163-1.
Then we have n^2 = (163-1)*(163-1) = 163^2 - 2*163 + 1 = 1 mod 163.
So, this part (one half) of the problem is solved.
We found two solutions in the given interval: n = 1 and n = 162.
(b) Now we want to prove that these two solutions, n= 1 and n= 162, are unique in the given interval
OK. Let assume that m is another integer number in the interval 0 <= m < 163,
inverse to itself mod 163. Then we have these two modular equations
m*m = 1 mod 163
1*1 = 1 mod 163.
Taking the difference, we have
(m+1)*(m-1) = 0 mod 163.
It means that either (m-1) or (m+1) is divisible by 163.
In combination with the fact that 0 <= m < 163, it means that either m= 1 or m= 162.
Thus we proved that in interval [0,163) there is no other own-inverse numbers mod 163
Problem 7I take a tablet every 10 days. If I take my first tablet on Monday and have 25 tablets,on what day will I take the last tablet ? Solution
+-------------------------------------------------------------------------------+
| To start solving, notice that taking a tablet every 10 days means |
| that the process of taking tablets is periodical with the period of 10 days. |
+-------------------------------------------------------------------------------+
Imagine that the days are coded in this natural way, using numbers from 1 to 7
instead of the days standard naming
Mo Tu We Th Fr Sa Su (*)
1 2 3 4 5 6 7
Next, imagine that you have long sequence of these numbers, repeating in this natural order
1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 . . . .
Then your day in this sequence is this coding number (10*24+1 mod 7)
(i.e. 24 intervals of 10 days plus the next day, and the sum is taken modulo 7).
Multiply 10*24 and add 1. You will get 241.
Find the remainder after division 241 by 7.
The division is 241 = 34*7 + 3.
Thus the remainder is 3.
In other words, (10*24+1 mod 7) = 3.
The remainder "3" is the code for the 3-rd day in the sequence (*).
Hence, you will take your last tablet on Wednesday.
Problem 8Find all integer numbers x for which x^3 = (x - 1)^3 + (x - 2)^3 + (x - 3)^3 + (x - 4)^3 + (x - 5)^3 + (x - 6)^3 + (x - 7)^3.Solution
Let's consider this equation
x^3 = (x - 1)^3 + (x - 2)^3 + (x - 3)^3 + (x - 4)^3 + (x - 5)^3 + (x - 6)^3 + (x - 7)^3. (1)
I am going to prove that there are no such integer numbers,
that satisfy this equation.
Let's consider the numbers modulo 3.
If x is divisible by 3, then the table for x-1, x-2, x-3, x-4, x-5, x-6 and x-7 mod 3 is this
x-1 x-2 x-3 x-4 x-5 x-6 x-7
mod 3 -1 1 0 -1 1 0 -1
The table for (x-1)^3, (x-2)^3, (x-3)^3, (x-4)^3, (x-5)^3, (x-6)^3 and (x-7)^3 mod 3 is this
(x-1)^3 (x-2)^3 (x-3)^3 (x-4)^3 (x-5)^3 (x-6)^3 (x-7)^3
mod 3 -1 1 0 -1 1 0 -1
The sum of remainders "mod 3" is -1 + 1 + 0 -1 + 1 + 0 -1 = -1,
while x^3 mod 3 is 0 in this case.
+-------------------------------------------------------------+
| It means that the sum in the right side of equation (1) |
| can not be equal to the left side: |
| they have different remainders when divided by 3. |
+-------------------------------------------------------------+
The same idea works for x = 1 mod 3. Indeed, then the tables are these
x-1 x-2 x-3 x-4 x-5 x-6 x-7
mod 3 0 -1 1 0 -1 1 0
The table for (x-1)^3, (x-2)^3, (x-3)^3, (x-4)^3, (x-5)^3, (x-6)^3 and (x-7)^3 mod 3 is this
(x-1)^3 (x-2)^3 (x-3)^3 (x-4)^3 (x-5)^3 (x-6)^3 (x-7)^3
mod 3 0 -1 1 0 -1 1 0
The sum of remainders "mod 3" is 0 - 1 + 1 + 0 - 1 + 1 + 0 = 0,
while x^3 mod 3 is 1 in this case.
+-------------------------------------------------------------+
| It means that the sum in the right side of equation (1) |
| can not be equal to the left side: |
| they have different remainders when divided by 3. |
+-------------------------------------------------------------+
The same idea works for x = 2 mod 3. Indeed, then the tables are these
x-1 x-2 x-3 x-4 x-5 x-6 x-7
mod 3 1 0 -1 1 0 -1 1
The table for (x-1)^3, (x-2)^3, (x-3)^3, (x-4)^3, (x-5)^3, (x-6)^3 and (x-7)^3 mod 3 is this
(x-1)^3 (x-2)^3 (x-3)^3 (x-4)^3 (x-5)^3 (x-6)^3 (x-7)^3
mod 3 1 0 -1 1 0 -1 1
The sum of remainders "mod 3" is 1 + 0 - 1 + 1 + 0 - 1 + 1 = 1,
while x^3 mod 3 is -1 in this case.
+-------------------------------------------------------------+
| It means that the sum in the right side of equation (1) |
| can not be equal to the left side: |
| they have different remainders when divided by 3. |
+-------------------------------------------------------------+
Thus, considering all possible case for (x mod 3), we proved that
equation (1) can not be valid.
It this point, the problem is solved completely.
ANSWER. The given equation has no solutions in integer numbers.
Problem 9Find the number of subsets of S = {1, 3, 8, 17, 30, 36, 47, 58},so that the sum of the elements in the subset is a multiple of 5. (Note that for the empty subset, we take the sum of the elements as 0.) Solution
The set of remainders of given numbers modulo 5 is
1 = 1 mod 5
3 = 3 mod 5
8 = 3 mod 5
17 = 2 mod 5
30 = 0 mod 5
36 = 1 mod 5
47 = 2 mod 5
58 = 3 mod 5
So, the list of remainders is {1, 3, 3, 2, 0, 1, 2, 3}, containing 8 elements.
I will introduce 7 integer numbers 'a', 'b', 'c', 'd', 'e', 'f', 'g', that may have values 0 or 1,
and will relate them to the remainders in the list according to this scheme
1 3 3 2 1 2 3
a b c d e f g
I intently missed the remainder '0' to simplify my reasoning.
I will explain it later what to do with the remainder '0'.
So, my numbers 'a', 'b', 'c', 'd', 'e', 'f', 'g' simply tell us, if the corresponding remainders
are included into the subsets or not.
Then the sum of remainders for any subset in the consideration is
a + 3b + 3c +2d + e + 2f + 3g (1)
with appropriate values of the coefficients.
My expression (1) is
a + e + 2(f+d) + 3(b+c+g). (2)
My task is to determine, how many different solutions (a,b,c,d,e,f,g) has this modular equation
a + e + 2(f+d) + 3(b+c+g) = 0 mod 5, (3)
if variables a, b, c, d, e, f and g may have the values 0 or 1.
In equation (3), we can consider 'a', 'b', 'f' and 'd' as free variables, giving them
the values 0 or 1 independently.
Then for each combinations of 'a', 'b', 'f' and 'd', we should find the number of solutions
to equation (3) for variables 'b', 'c' and 'g'.
I organized my calculations in Excel table, which is shown below.
In the table, first 4 columns and 16 lines represent all possible values of variables a, e, f and d.
The fifth column is the computed sum a + e + 2(f+d).
The sixth column is the expression 3(b+c+g) = -(a + e + 2(f+d)) mod 5, according to equation (3).
Comparing with the column(5), column (6) has the opposite signs.
Column (7) is the column (6) taken mod 5.
(1) (2) (3) (4) (5) (6) (7) (8) (9)
a e f d a+e+2(f+d) -(a+e+2(f+d)) -(a+e+2(f+d)) mod 5 b+c+g mod 5 number of solutions
= -3(b+c+g) = 3(b+c+g) = 3(b+c+g) mod 5 in b, c, g
-------------------------------------------------------------------------------------------------------------------------
0 0 0 0 0 0 0 0 1
1 0 0 0 1 -1 4 3 1
0 1 0 0 1 -1 4 3 1
1 1 0 0 2 -2 3 1 3
0 0 1 0 2 -2 3 1 3
1 0 1 0 3 -3 2 4 0
0 1 1 0 3 -3 2 4 0
1 1 1 0 4 -4 1 2 3
0 0 0 1 2 -2 3 1 3
1 0 0 1 3 -3 2 4 0
0 1 0 1 3 -3 2 4 0
1 1 0 1 4 -4 1 2 3
0 0 1 1 4 -4 1 2 3
1 0 1 1 5 -5 0 0 1
0 1 1 1 5 -5 0 0 1
1 1 1 1 6 -6 4 3 1
24 <<<---sum
So, again, the columns (1) - (4) are free variables; the column (5), (6) and (7) are simple straightforward calculations.
Only columns (8) and (9) require explanations.
To get the number in column (8), we should take the corresponding number from column 7 (let call it z)
and solve equation 3x = z mod 5. Then the found x mod 5 goes to column (8).
It is because from the number 3(b+c+g) mod 5 in the column (7) we want to get b+c+g in column (8).
To get the number in first row of column 9, we consider the number in the first row of column 8, which is 0.
This 'zero' is the right side of the equation b+c+g = 0 mod 5 from equation (3).
In variables 'b', 'c', 'g' with the values (0, 1), it has only one solution mod 5. This solution is (b=0, c=0, g=0).
So, we write the number 1 (the number of solutions) in the cell (9,1).
To get the number in second row of column 9, we consider the number in the second row of column 8, which is 3.
This 'three' is the right side of the equation b+c+g = 3 mod 5 from equation (3).
In variables 'b', 'c', 'g' with the values (0, 1), it only one solutions mod 5. This solution is (b=1, c=1, g=1).
So, we write the number 1 (the number of solutions) in the cell (9,2).
In the cell (9,3), we have the same situation. So, the number in (9,3) is 1, again.
In the cell (8,4), we have the number '1'.
This 'one' is the right side of the equation b+c+g = 1 mod 5 from equation (3).
In variables 'b', 'c', 'g' with the values (0, 1), it has three solution mod 5.
These solutions are (b=1, c=0, g=0), (b=0, c=1, g=0), (b=0, c=0, g=1).
So, we write the number 3 (the number of solutions) in the cell (9,4).
In the cell (9,5), we have the same situation. So, the number in (9,5) is 3, again.
In the cell (8,6), we have the number '4'.
This 'four' is the right side of the equation b+c+g = 4 mod 5 from equation (3).
In variables 'b', 'c', 'g' with the values (0, 1), it HAS NO solutions mod 5.
So, we write the number 0 (the number of solutions) in the cell (9,6).
In the cell (9,7), we have the same situation. So, the number in (9,7) is 0, again.
In the cell (8,8), we have the number '2'.
This 'two' is the right side of the equation b+c+g = 2 mod 5 from equation (3).
In variables 'b', 'c', 'g' with the values (0, 1), it has three solution mod 5.
These solutions are (b=1, c=1, g=0), (b=1, c=0, g=1), (b=0, c=1, g=1).
So, we write the number 3 (the number of solutions) in the cell (9,8).
I will stop my explanations for column (9) at this point. The rest of values in column (9) simply repeat
the situations described for (9,1), (9,2),(9,3), (9,4), (9,5), (9,6), (9,7), (9,8).
The number 24 at the bottom of the 9-th column is the sum of values in this column. It is nothing else as
the total number of solutions to equation (3).
Thus, so far, there are 24 subsets, satisfying the problem's condition, if do not involve the remainder 0 mod 5,
which corresponds to number 30.
Notice that one of these 24 cases corresponds to the empty subset.
It is the case when all coefficients are zeroes a = e = f = d = 0.
In this case, the rest of coefficients ALSO are zeroes b = c = g = 0 in the cell (9,1), according to the solution.
So, we found 23 non-empty subsets and the 24-th subset, which is empty.
Now, with the number 30 and with individual subset {30}, it doubles 23 subsets to 46 subsets and adds the subset {30}.
In all, we have now (2*23 + 1) + 1 = 48 sub-sets (47 non-empty subsets PLUS one empty subset).
Here '+1' in parentheses corresponds to the individual subset {30}.
ANSWER. In all, there are 48 subsets, satisfying the problem's conditions.
My other lessons in this site on miscellaneous problems on divisibility of integer numbers are - Light flashes on a Christmas tree and a Least Common Multiple - The number that leaves a remainder 1 when divided by 2, by 3, by 4, by 5 and so on until 9 - The number which gives remainder 4 when divided by 7, remainder 5 when divided by 8 and remainder 6 when divided by 9 - Introductory problems on divisibility of integer numbers - Finding Greatest Common Divisor of integer numbers - Relatively prime numbers help to solve the problem - Solving equations in integer numbers - Quadratic polynomial with odd integer coefficients can not have a rational root - Proving an equation has no integer solutions - Composite number of the form (4n+3) must have a prime divisor of the form (4n+3) - Problems on divisors of a given number - How many three-digit numbers are multiples of both 5 and 7? - How many 3-digit numbers are not divisible by 2; not divisible by 3; not divisible by either 2 or 3 - How many integer numbers in the range 1-300 are divisible by at least one of the integers 4, 6 and 15 ? - Find the remainder of division - Why 3^n + 7^n - 2 is divisible by 8 for all positive integer n ? - What is the last digit of the number a^n ? - Find the last three digits of these numbers - Find the last two digits of the number 3^123 + 7^123 + 9^123 - Find the last two digits of (1! + 2! + 3! + ... + 2024!)^2024 - Find n-th term of a sequence - Solving Diophantine equations - How many integers of the form n^2 + 18n + 13 are perfect squares - Miscellaneous problems on divisibility numbers - Find the sum of digits of integer numbers - Two-digit numbers with digit "9" - Find a triangle with integer side lengths and integer area - Math circle level problem on the hundred-handed monster Briareus - Math Circle level problem on lockers and divisors of integer numbers - Nice entertainment problems related to divisibility properties - Using the little Fermat's theorem to solve a problem on modular arithmetic - OVERVIEW of miscellaneous solved problems on divisibility of integer numbers This lesson has been accessed 1967 times. |
