Hi I got two tasks which I have some trouble with. 1) A guy has 1770 dollars to shop food for. One bread costs 31 dollars and a jar of jam costs 21 dollars. How many loafs of bread and jar's of jam can the guy buy? I'm suppose to calculate it using Euler Algebra 31x + 21y = 1770 Do I solve this by guessing x,y ? 2) a) Show that an integer, is congruent 3 mod 4, and which has a prime factor which is congruent modulo with 4. How do I do that? b) show that infinit many prime numbers are congruent 3 mod 4. Solution (1) I calculate, gcd(21,31) 31=1*21+10 21= 2*10+1 10= 9*1+0 Thus, gcd(21,31)=1 Working backwards, 21-2*10=1 21-2(31-1*21)=1 Thus, 21-2*31+2*21=1 Thus, 21(3)+31(-2)=1 Thus, 21(5310)+31(-3540)=1770 So, x=5310 and y=-3540 Is one solution of, 21x+31y=1770 Thus, all solutions are: x=5310+31t y=-3540-21t We require that, x,y>0 Thus, 5310+31t>0 -3540-21t>0 Solving both of these inequalities we get, t>-171.2 t<-168.5 Thus, -171.2<t<-168.6 Since t is in integer I have, t=-171,-170,-169 Corresponding to 3 solution of x and y which are: (x,y)=(9,51) (x,y)=(40,30) (x,y)=(71,9) Altenate Solution for (1) I have: .. 31x + 21y .= .1770 .[1] Then: . . . .31x - 1770 .= .-21y By definition: . . . 31x .= .1770 (mod 21) And I have: . . . 10x .= .6 (mod 21) Divide by 2: . . . . . 5x .= .3 (mod 21) Multiply by 17: . 17·5x .= .17·3 (mod 21) and I have: . . . 85x .= .51 (mod 21) which equals: . . . . .x .= .9 (mod 21) Hence: . x .= .9 + 21k . for some integer k. Substitute into [1]: . 31(9 + 21k) + 21y .= .1770 . → . y .= .71 - 31k There are three solutions. If k = 0: .(x,y) = (9,71) If k = 1: .(x,y) = (30,40) If k = 2: .(x,y) = (51,9) Which of my two solutions for (1) is best? Solution (2) Actually I know I can use Dirichlet's Theorem. (One of my favorite mathemations). But, my professor says I need to prove this without that. --- Assume there are finitely many primes of form 4k+3 P1 P2 P3 ... Pn Form the number, N=4*P1*P2*...*Pn-1=4(P1*P2*...*Pn-1)+3 Prime factorize this number, N=Q1*Q2*...*Qm Since, N is odd it is either of form 4k+1 or 4k+3 But, N takes the form of4k+3. Now, if all Qk's in the factorization have form 4k+1 Then, N would have form 4k+1 (As explained in other post). Which is not true, thus it must have at least one prime Qk which is of form 4k+3. Since we have equality and the left is divisible by Qk so does the right. But since P1*P2*...*Pn contains all primes of form 4k+3 it is divisible by Qk. But then Qk divide 1!!!! which is impossible. Thus, there most be infinitely many (OR NONE) primes in form of 4k+3. I know proof is not well formulated, but is there anybody here who maybe could assist me in making it better? Cheers. Mathboy