Section 4.2

29: By "strong" induction. If n=1, it's clear that n can be uniquely
written as a sum of distinct powers of 2, namely n=2^0.

For n>1, subtract from n the largest power of 2 not exceeding it:
n'=n-2^a. Observation: 2n'<n. Indeed, if 2n'-n=2n-2*2^a-n=n-2^(a+1) were
positive, we should have picked a differently in the first place.

Thus, we can use the inductive hypothesis on n' (one can write n' as
sum of distinct powers of 2) and the biggest power that fits into n'
is smaller than the biggest power that fits into n. So, the claim
follows for n. 

32: 10=-1 mod 11, so if n=a_0 + a_1 * 10^1 + a_2 * 10^2+... then, mod
11, n=a_0+a_1*(-1)+a_2*(-1)^2+...=a_0-a_1+a_2-...

This is zero if and only if the alternating sum of the a_i is
divisible by 11.



Section 4.3: 

12: the numbers (n+1)! and i have (for i=2...n+1) the common factor
i. So, (n+1)!+i is composite.

23: Let n be one of 1,..,p^k-1. p^k is divided only by powers of p, so
in order to be relatively prime to p^k one merely needs to not be
divisible by p. How many numbers n ARE divisible? One in every p, so
p^k/p=p^(k-1). Thus, phi(p^k)=p^k-p^(k-1).

30: We need, for each prime p, to find out how many times p divides
the lcm. Say p=2. The sum of the exponents over 2 in a and b is 7,
while their minimum is 3. Which two numbers have sum 7 and minimum 3?
Answer: 3 and 4. So, 2^3 divides on factor and 2^4 the other. So, the
lcm is divisible by 2^4. Etc. One gets: 2^4*4^4*5^1*7^11.

36: Let q be a variable. Let m, n be nonnegative integers with n<a. It
  is easy to check the following identity:
  q^(m*a+n)-1=(q^a-1)(q^(m*a+n-a)+q^(m*a+n-2a)+q^(m*a+n-3a)+...+q^n)+q^n-1.
  The solution follwos from this. 

43: 144=1*89+ 55
     89=1*55+ 34
     55=1*34+ 21
     34=1*21+ 13
     21=1*13 +8
     13=1*8 +5
      8=1*5 +3
      5=1*3 +2
      3=1*2 +1
So 1 is the gcd. 
    1=3-2
     =3-(5-3)
     =(8-5)-(5-(8-5))
     =...
     =34*144-55*89


Section 4.4

32: We want to solve x=0 mod 5, x=1 mod 3. In notation of the
theorem, m_1=5, m_2=3. a_1=0, a_2=1. M_1=3, M_2=5. y_1=2, y_2=2.
x=a_1M_1y_1+a_2M_2y_2=0+10 mod 15. So we are talking about 10, 25, 40,
..., i*15+10,...