I am a number less than 3,000.When you divide me by 32, my remainder is 30. When you divide me by 58, my remainder is 44. What number am I.
I found 3 of them:
798 , 1726, and 2654
How?
Using a silly very old computer language program from the 80's called BASIC
1 dim x(100),y(100)
10 for n = 1 to 100
20 x(n) = 32*n+30
30 y(n) = 58*n+44
50 next n
60 for k = 1 to 100
70 for l = 1 to 100
80 if x(k) = y(l) then print x(k)
90 next l
100 next k
>run
798
1726
2654
I do not understand I have a calculator right next to me and none of those answers made any sense
To find the number, we can set up a system of equations based on the given information.
Let's assume the number is "x".
According to the given information:
x ≡ 30 (mod 32) -- Equation 1
x ≡ 44 (mod 58) -- Equation 2
Now, let's solve this system of linear congruences using the Chinese Remainder Theorem (CRT).
Step 1: Solve Equation 1 for x.
x ≡ 30 (mod 32)
x = 30 + 32k -- Equation 3 (k is an integer)
Step 2: Substitute Equation 3 into Equation 2.
30 + 32k ≡ 44 (mod 58)
Step 3: Simplify Equation 2 and solve for k.
32k ≡ 44 - 30 (mod 58)
32k ≡ 14 (mod 58)
To find the modular inverse of 32 (mod 58), we can use the Extended Euclidean Algorithm.
58 = 32(1) + 26
32 = 26(1) + 6
26 = 6(4) + 2
6 = 2(3) + 0
From this, we see that the modular inverse of 32 (mod 58) is 15.
Multiplying both sides of the congruence by the modular inverse:
15(32k) ≡ 15(14) (mod 58)
480k ≡ 210 (mod 58)
Step 4: Simplify the congruence.
480k ≡ 210 (mod 58)
44k ≡ 28 (mod 58) -- Equation 4
Step 5: Solve Equation 4 for k.
To find the modular inverse of 44 (mod 58), we can use the Extended Euclidean Algorithm.
58 = 44(1) + 14
44 = 14(3) + 2
14 = 2(7) + 0
From this, we see that the modular inverse of 44 (mod 58) is 41.
Multiplying both sides of the congruence by the modular inverse:
41(44k) ≡ 41(28) (mod 58)
1804k ≡ 1148 (mod 58)
Step 6: Simplify the congruence.
1804k ≡ 1148 (mod 58)
12k ≡ 34 (mod 58) -- Equation 5
Step 7: Solve Equation 5 for k.
To find the modular inverse of 12 (mod 58), we can use the Extended Euclidean Algorithm.
58 = 12(4) + 10
12 = 10(1) + 2
10 = 2(5) + 0
From this, we see that the modular inverse of 12 (mod 58) is 45.
Multiplying both sides of the congruence by the modular inverse:
45(12k) ≡ 45(34) (mod 58)
540k ≡ 1530 (mod 58)
Step 8: Simplify the congruence.
540k ≡ 1530 (mod 58)
20k ≡ 14 (mod 58) -- Equation 6
To solve Equation 6, we can use trial and error or substituting values for k to find a solution.
By substituting k = 42, we can check if it satisfies Equation 6:
20(42) ≡ 14 (mod 58)
840 ≡ 14 (mod 58)
14 ≡ 14 (mod 58)
Therefore, k = 42 is a valid solution.
Step 9: Substitute the value of k into Equation 3 to find the value of x.
x = 30 + 32k
x = 30 + 32(42)
x = 30 + 1344
x = 1374
Therefore, the number you are looking for is 1374.
To find the number, we can set up a system of equations. Let's call the number we are trying to find "x".
From the first condition, when x is divided by 32, the remainder is 30. This can be expressed as:
x ≡ 30 (mod 32)
Similarly, from the second condition, when x is divided by 58, the remainder is 44. This can be expressed as:
x ≡ 44 (mod 58)
To find the value of x, we can solve this system of modular equations simultaneously. One way to solve this is by using the Chinese Remainder Theorem (CRT).
First, let's find the modular multiplicative inverse of both 32 and 58 modulo each other.
Using the Extended Euclidean Algorithm, we find:
- The modular inverse of 32 modulo 58 is 29.
- The modular inverse of 58 modulo 32 is 26.
Now, we can apply the CRT:
x = (30 * 58 * 26 + 44 * 32 * 29) % (32 * 58)
Calculating this expression, we find that x is equal to 1314.