# Thread: Euler Algebra and Prime numbers

1. ## 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.

2. Originally Posted by MT20
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)

3. Originally Posted by MT20
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.

4. [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: . 17·5x .= .17·3 (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)

5. 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

6. Originally Posted by MT20
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.

7. 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