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 | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Euler: Please verify my result !

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**