Euler: Please verify my result !

  1. 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
     
  2. jcsd
Know someone interested in this topic? Share this thead via email, Google+, Twitter, or Facebook

Have something to add?

0
Draft saved Draft deleted