
#1
Oct1106, 09:00 AM

P: 30

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, 212*10=1 212(311*21)=1 Thus, 212*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=354021t We require that, x,y>0 Thus, 5310+31t>0 354021t>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*...*Pn1=4(P1*P2*...*Pn1)+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 


Register to reply 
Related Discussions  
Can you verify this please???  Calculus  3  
Stochashic variable result(Please verify) Urgent  Calculus & Beyond Homework  0  
Results same w/ Euler, Improved Euler, & RungeKutta  Differential Equations  14  
can someone verify this  Calculus & Beyond Homework  0  
Someone verify?  Introductory Physics Homework  8 