Results 1 to 7 of 7

Math Help - Euler Algebra and Prime numbers

  1. #1
    Newbie
    Joined
    Sep 2006
    Posts
    4

    Euler Algebra and Prime numbers

    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.

    Any idears?

    Sincerely Yours MT

    p.s. I'm going to hospital tomorrow for a operation with my heart, so therefore I hope that there is somebody out who could be so kind to help me answer these two questions.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by MT20 View Post
    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
    .
    I never heard of Euler Algebra but I know what you are talking about.

    One way is countinued fractions, but I will use the backwards way of Euclidean Algorithm.

    We 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 we 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)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by MT20 View Post
    Hi
    a) Show that an integer, is congruent 3 mod 4, and which has a prime factor which is congruent modulo with 4.
    Since we are talking about odd primes over here they can only have one of two forms:
    4k+1 or 4k+3

    If n and m are two numbers of form 4k+1 then nm is also of form 4k+1.

    Now, if a number is of the form 4k+3 (which is what the problem says) then all primes cannot have form 4k+1 because that would mean a number is of form 4k+1 which it is not.


    b) show that infinit many prime numbers are congruent 3 mod 4.
    I try to post a proof later, but not now.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,706
    Thanks
    625
    [size=3]Hello, MT20![/soze]

    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?

    Do I solve this by guessing x,y ?
    Certainly not! . . . I wouldn't call that "solving", would you?
    Why not use their instructions (Euler algebra)?

    I too am not familiar with "Euler algebra".
    If it is Modular Arithmetic, I have a solution.
    [I'll use "=" for equivalence.]

    We have: .. 31x + 21y .= .1770 .[1]

    Then: . . . .31x - 1770 .= .-21y

    By definition: . . . 31x .= .1770 (mod 21)

    And we have: . . . 10x .= .6 (mod 21)

    Divide by 2: . . . . . 5x .= .3 (mod 21)

    Multiply by 17: . 175x .= .173 (mod 21)

    and we 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)

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2006
    Posts
    4
    I'm packing my bags for my hospital stay as of now. But first I would like to say thank You for You VERY MUCH for Your help.

    I will look if for the proof later today.

    Sincerely Yours
    MT20
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by MT20 View Post
    I will look if for the proof later today.
    Actually you can use Dirichlet's Theorem. (One of my favorite mathemations).
    But, we assume 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.

    The beauty of this proof is the type. In mathematics there are constructive proofs and existence proofs. The former is a proof which gaurenntees something by showing how to arrive at a solution. The latter does not show how to arrive at a solution but amazing says the solution exists (which is all what mathematicians care about). For example, the fundamental theorem of algebra does not show how to solve a polynomial but promisies that we can solve it. I am just saying this because of how much I like existence proofs.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Sep 2006
    Posts
    4
    Hello again,

    Thank You very much for Your help.

    I have two final questions before I go. Hope thats okay.

    a) Need help to construct a set of RSA keys. Use these keys for encryption, decryption and signing of message.

    Any idears on howto does this as simply as possible?

    b)

    How do I solve the equation x^7 congruent 21 modulo 66

    Any idears on howto solve this ?

    I thank you again for Your help.

    Sincerely Yours
    MT20
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. euler fhi function and power of a prime
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 1st 2011, 12:09 PM
  2. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  3. [SOLVED] Euler Identity Algebra Problem
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: August 30th 2011, 11:53 AM
  4. Euler numbers generating sequence radius of convergence
    Posted in the Advanced Math Topics Forum
    Replies: 9
    Last Post: November 26th 2010, 12:50 AM

Search Tags


/mathhelpforum @mathhelpforum