| re. .1
Yes, positive integer is what I was looking for. Even thou your
answer is correct, I was more interested in the method used to derive
your answer. Could you provide with the reasoning.
Thanks,
Kostas
|
| Re .2:
Start by writing the first two rows:
31 1
29 0
2 1
The third row is obtained by dividing 31 by 29 and getting the integer
result of 1. Then subtract 1 times the second row from the first
row, yielding the third row. Repeat this using the last two rows.
Dividing 29 by 2 yields 14, so we get:
1 -14
Since the first number is now one, we will stop. (If it becomes
zero before it becomes one, the original numbers were not relatively
prime and other concerns must be addressed.)
Observe that when the number in the second column on any selected row
is multiplied by the first number of the first row, it is always
congruent to the number in the first column of the selected row,
modulo the first number of the second row. The proof is left as
an exercise for the reader.
We know now that -14*31 is congruent to 1, modulo 29. To find a
positive number with this property, add 29 to 14. 15*31 is congruent
to 1. To get a number congruent to 7 mod 29, multiply 15 by 7 to
get 105. To reduce this number, find the remainder when divided
by 29, 18. 18*31 is congruent to 7 mod 29.
However, 18*31 is congruent to 0 mod 31, as is anything times 31.
We want something congruent to 13. Well, let's use 13 plus something
congruent to 0 mod 31. To make it congruent to 7 mod 29, let's
make that something also congruent to (7-13) mod 29. (-14*-6)*31
is congruent to -6 mod 29. -14*-6 is 84. The remainder when 84
is divided by 29 is 26, so 26*31 is congruent to -6 mod 29.
So 13 + (26*31) = 819 is congruent to 13 mod 31 and 7 mod 29.
In fact, any number congruent to 819 mod 29*31 has this property.
29*31 is 899, so let's repeat this process with 899 and 30:
899 1
30 0
29 1
1 -1
So -1*899 is congruent to 1 mod 30. To get a number congruent to
819 mod 899 and 11 mod 30, we use 819 + (11-819)*(-1)*899. This
is 727211. Taking the remainder when divided by 899*30, we get
25911.
-- edp
|
| re. .3
I just realized that I did not give my answer to this problem, which
is different than your method.
Here we go:
The problem is to find the smallest number which divided by 29 gives
a remainder of 7, divided by 30 gives a remainder of 11, and divided
by 31 gives a remainder of 13.
If we let the quotients be a, b, and c
then the number is equal to any one of these quantities
29a + 7 = 30b + 11 = 31c + 13
whence
30b - 29a = -4 and 31c - 29a = -6
since a = b = 1 makes | since c = a = 2 makes
30b - 29a = 1 | 31c - 29a = 2
it follows that | it follows that
a = b = -4 which | c = a = -3 which
makes | makes
30b - 29a = -4 | 31c - 29a = -6
But these do not give the only values of a, b, and c that
satisfy the two equations.
Concider
a = -4 + 30x a = -3 + 31y
b = -4 + 29x c = -3 + 29y
these are the general integral values that satisfy the two equations,
and they gives us, equating the values of a,
31y - 30x = -1
the obvious solution is x = y = -1
but again we generalize
x = -1 + 31z
y = -1 + 30z
for a, this gives -4 + 30*(-1 + 31z) = -34 +930z
and for the required number, this gives
29*(-34 + 930z) + 7
= -986 + 26970 + 7
= 26970z - 979
the smallest positive value is obtained by putting z = 1 ,
which gives 25991.
It can be verified that 25991 is equal to
29 * (896) + 7
or
30 * (866) + 11
or
31 * (838) + 13
Enjoy,
Kostas G.
|