%These are solutions to the  HW#2  problems     Sat, Jan 31, 1998
%  using  MATLAB 5  
%  Problem 1. Solve      156x=183  (mod  201).
%     The above equation is equivalent to  52x=61 (mod 67)
%     Solution #1.
x=0:66; %  - These are all possible solutions mod 67
y=find(mod(52*x,67)==61)
y =
    55
%%%%%%%     ANSWER to  Problem 1:   x=55  (mod 67)
%%%%%%%     REMARK. It is not surprizing that the solution is unique.
%%%%%%%        This is because  
gcd(52,67)
ans =
     1

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%$$    Problem 2. Solve      36x=24  (mod  64).
%%%%%        First we compute
gcd(36,64)
ans =
     4
%%%%%   The original equation is equivalent to   9x=6  (mod 16).
%%%%%   Since   (9,16)=1,  we can divide by  3.
%%%%%   3x=2  (mod 16). The solution is unique and it is  18/3=6.
%%%%%          Answer:  x=6  (mod 16)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%    Problem 3. Solve   12x+17y=400  in pos. integers.
%%%%%    Possible  x's are in the range
x=0:400/12;
%%%%%    Then the value for  17y   will be
z=400-12*x;
%%%%%    Finding the "good places", i.e. the places for which  z=17y  is both positive and  0  mod 17.
p=find(z>0 & mod(z,17)==0)
p =
     6    23
x=x(p)
x =
     5    22
%%%%%    the corresponding  y's  can be found by

y=z(p)/17
y =
    20     8
%%%  Thus there are two solutions  (x,y),  (5,20)  and  (22, 8).  
%%%  These are given by the columns of the matrix
[x;y]
ans =
     5    22
    20     8
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%$$$$$$$    Problem 4.  Find all integers   x, 1<x<3000000,
%%%%%%%%       s.t.   x = 1 (mod 101),  x = 2 (mod 102),  x = 3 (mod 103).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
x=1:3000000;
p=find(mod(x,101)==1);
??? Error using ==> ones
Out of memory. Type HELP MEMORY for your options.

Error in ==> Macintosh HD:MATLAB 5:Toolbox:matlab:elfun:mod.m
On line 26  ==>    y = y(ones(size(x)));

%%%%%  -  Problem - not enough memory. 
%%%%%  -  However,  there is a simple approach requiring less memory.
x=1:101:2999999;  %%%%%  these are all  x's  in our range for which  x=1  (mod 101)
length(x)
ans =
       29703
%%%%%%   This is much better: the length of the array is <30000
x=x(find(mod(x,102)==2));
length(x)
ans =
   291
%%%%%%   It turns out that there are  291   x's  in our range satisfying the first two conditions
%%%%%%   Now we take care of the last condition   x = 3 (mod 103).
x=x(find(mod(x,103)==3))
x =
     1061006     2122112
%%%%%%%%     Answer to PROBLEM 4:  Two solutions, x=1061006  and   x=2122112.
%%%%%%%%     This is the end of the Homework #2.
diary off