Hi(adsbygoogle = window.adsbygoogle || []).push({});

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

**Physics Forums - The Fusion of Science and Community**

# Euler: Please verify my result !

Know someone interested in this topic? Share a link to this question via email,
Google+,
Twitter, or
Facebook

Have something to add?

- Similar discussions for: Euler: Please verify my result !

Loading...

**Physics Forums - The Fusion of Science and Community**