1. 2 More Questions

1. Find all solutions, if any, to the system of congruences.

x = 5 (mod 6)
x = 3 (mod 10)
x = 8 (mod 15)

I tried following an example out of my book and got the following, which I'm fairly sure is horribly wrong:

m = 900; M1 = 150; M2 = 90; M3 = 60
150 = a mod 6; a = 12;
90 = b mod 10; b = 20;
60 = c mod 15; c = 30;

z = 5*150*12 + 3*90*20 + 8*60*30
z = 28,800

z = x (mod m)
28,800 = x (mod 900)
so... x = 900. This, doesn't seem right, any help would be appreciated.

2. Use Strong induction to show that every positive integer n can be written as a combination of distinct powers of 2. Ex. $2^0 = 1, 2^1 = 2, 2^2 = 4$.

Here's what I have. I think I have proven it, but I'm not sure if it's by strong induction.

Basis: $2^0 = 1$

Inductive:
Assume: $2^x + 2^y = j$
We must show $2^x + 2^y = (j+1)$

if (j+1) is odd. $x = (j+1)/2$ rounded down. y = 0.
/* ie. for $j = 2, x = 1, y = 0$; */

if (j+1) is even. $x = (j+1)/2 - 2, y = 1$;

Thus we have shown that the basis and inductive steps are true.

2. Originally Posted by Niotsueq
1. Find all solutions, if any, to the system of congruences.

x = 5 (mod 6)
x = 3 (mod 10)
x = 8 (mod 15)
As a very quick check, you should recognize that the one's digit must be a 3. Your number x must end with a three.

x = 3 mod 10