Good job, Yura! I hope you will have a wonderful time in the future! -Kevin

Great material, relatively good text, confusing lectures, terrible TA, nightmare midterm, fair exam. Good times. Congrats to all who survived. spot on!

*Is the median for the course really a C-? That is actually the LOWEST mark i have ever seen for a 300 level Math class! Can we curve it to at least a B-?

Here's the grade distribution for the course:

90 - 100

12

80 - 89

17

70 - 79

8

60 - 69

19

50 - 59

17

40 - 49

3

30 - 39

4

20 - 29

2

10 - 19

1

0 - 9

1

As you see we have 35% of A-, A, A+ grades, the maximum allowed for a course. The fact that we have many students who got a mark below 50 (which means 0-25 on the final exam) does lower the statistics, but doesn't change the fact that the exam and the midterm have been a fair measurement of students' ability to solve problems and apply the material of the course. Once again, I can't curve the grades once I have 35% of A-,A,A+ grades.

LOL. We had 2 TAs: male and female, I think one of them was actually good.
Sorry for confusing you in the lectures. Yura.

x^2= 5 mod (2^13 -1) prime modulus...find all solutions to this congruence
A:
here (2^13) - 1 is prime now note 2^13 - 1 is odd and since (2^13) - 1 = 1 mod 5 then (5/p) = 1 hence 5 is a QR mod (2^13) - 1
now note (2^13) - 1 = 3 mod 4 hence by question 6 page 184
x = 5^[( 2^13)/4] is a solution to x^2 = 5 mod (2^13 - 1)
one solution is x = 5^(2^11)

Q: Professor, are you going to hold office hours this Thursday from 10.30 to 12.30?

A: No

Q: From our midterm 3a, the solution says " let a be a primitive root mod 43. Then x1,....x7=1, a^6,....,a^36 mod 43", why is this true? Can you explain the steps in detail?

A: I'm not the prof, so I may be wrong. I think it's because since a is a primitive root, we must have a^k=x for each x1, x2, ..., x7. But we have x^7 = 1mod43 => a^k7 = 1mod43 (by substituting x=a^k). But since a is a primitive root, we know that only a^42=1mod43 and since 6*7 = 42, we must thus have 6|k. Therefore we have x1 = 1 = a^0, x2 = a^6, x3 = a^6*2= a^12, ..., x7 = a^6*6 = a^36. can't it be argued that 7 is the order, and hence 7k should divide 42, which is p-1?\

x^2= 5 mod (2^13 -1) prime modulus...find all solutions to this congruence
A:
here (2^13) - 1 is prime now note 2^13 - 1 is odd and since (2^13) - 1 = 1 mod 5 then (5/p) = 1 hence 5 is a QR mod (2^13) - 1
now note (2^13) - 1 = 3 mod 4 hence by question 6 page 184
x = 5^[( 2^13)/4] is a solution to x^2 = 5 mod (2^13 - 1)
one solution is x = 5^(2^11)

Q: Professor, are you going to hold office hours this Thursday from 10.30 to 12.30?

A: No

Q: From our midterm 3a, the solution says " let a be a primitive root mod 43. Then x1,....x7=1, a^6,....,a^36 mod 43", why is this true? Can you explain the steps in detail?

A: I'm not the prof, so I may be wrong. I think it's because since a is a primitive root, we must have a^k=x for each x1, x2, ..., x7. But we have x^7 = 1mod43 => a^k7 = 1mod43 (by substituting x=a^k). But since a is a primitive root, we know that only a^42=1mod43 and since 6*7 = 42, we must thus have 6|k. Therefore we have x1 = 1 = a^0, x2 = a^6, x3 = a^6*2= a^12, ..., x7 = a^6*6 = a^36. can't it be argued that 7 is the order, and hence 7k should divide 42, which is p-1?

Q: if n is an integer s.t n > 1 then n does not divide (2^n) - 1

A: suppose p is the smallest prime divisor of n in the factorization of n into distinct primes then gcd (n , p - 1) = 1 hence there are integers k and s such that n(s) + k(p - 1) = 1. now suppose p divides (2^n) - 1 then 2^n = 1 mod p and since p does not divide 2 then 2^( p - 1) = 1 mod p but 2 = 2^( n(s) + k( p - 1)) = (2^ n)(s)) ( 2^( p - 1)(k)) = 1 mod p contradiction hence p does not divide (2^n) - 1 and since p is the smallest divisor of n, n does not divide (2^n) - 1

Q: prove a^(2^n) = 1 mod 2^(n + 2) where a is odd

A: suppose a is odd then a = 2k + 1 k integer now 2^n = 2( 2^(n-1)) hence a^(2^n) = (a^2)(2^(n -1)). now 2^(n + 2) = 4(2^n) and a^2 = 4k^2 + 4k + 1 hence a^2 = 1 mod 2^(n + 2) a^2(2^(n - 1)) = 1^(2^(n - 1)) = 1 mod 2^( n + 2) hence a^(2^n) = a^2(2^( n - 1)) =1 mod 2^( n + 2)

how do you approach a question like 3x^2 + 5x +1=0 mod 199(prime) ? this is what i tried: made 5x as 204 which would be divisible by 3...then by some algebra and completing the square, i ended up with (x+34)^2=28 mod199 i checked if 28 was QRmod 199..it was, then i got y^2=28 mod199. where y=x+34 can't seem to continue to find a value for y since exponent 2 is not rel. prime with 198(phi199)..please advise, many thanks!

Q; How to solve x^3 = 8 mod 13?

Q: Is there going to be a particular emphasis on the material covered since the midterm or is it going to be evenly distributed throughout the whole course?

Q: Is it possible to update the section on "What we actually covered?" just to be sure we don't leave out anything that we should study for, or study what we didn't cover? Also, in regards to Lecture 19 (not on exam)..what *date* was it taught? Just to confirm.

Q: prove y^2 = x^3 + 7 has no integer solutions

A: suppose ( x , y) is a integer solution such that x is even then let x = 2k then x^3 + 7 = 4(2k^3) + 7 hence y^2 is odd.

let y = 2j + 1 then y^2 = 4(j^2 +j ) +1 = 4(2k^3) + 7 and so dividing by 4 on both sides gives a remainder of 7 on one side and 1 on the other sidecontradiction and so x is odd.

now y^2 + 1 = x^3 +8 = ( x +2 )( x^2 -2x + 4)

since x is odd x^2 - 2x + 4 = 3 mod 4. Now suppose q is prime such that q = 3 mod 4 and q does not divide x^2 - 2x + 4then x^2 -2x + 4 is not equal to m( 3 + 4r ) for r,m integers contradiction since x^2 - 2x + 4 = 3 mod 4. There is a prime q such that q dividesx^2 - 2x + 4.

now consider y^2 + 1 = x^3 + 8 mod q

here q divides x^3 + 8 since q divides x^2 -2x + 4 and so y^2 + 1 = 0 mod q and so -1 is a QR mod q then since q is odd (-1)^(q-1)/2 = 1 mod qby Eulers criterion but (q-1)/2 = 1 + 2p hence (-1)^(q-1)/2 = -1 contradiction

Hence y^2 = x^3 + 7 has no integer solutions (Anthony)

Q:
Show that the equation x2 ≡ a mod 21 has either 1, 2 or 4 solutions modulo 21.

Q: are there any tricks of factoring Gaussian integers like 1+3i and 3+4i? other than by trial and error?

Q: For the proof of the question "If A Gaussian integer Z is a Gaussian prime, then N(Z) is a prime or a square o a prime of the form p=4k+3", we have the following sentence from the answer below: " If z is not an integer then z divides a product of primes in the integers." Can someone explain why we have this causation?

A: Here z divides a product of primes in the integers because (z) ( conjugate of z) = N( z ) and so by the unique factorization in the guassian integers z must divide a prime in the Integers ( Anthony)

Q: Is it possible to update the section on "What we actually covered?" just to be sure we don't leave out anything that we should study for, or study what we didn't cover? Also, in regards to Lecture 19 (not on exam)..what *date* was it taught? Just to confirm.

Q: I know you said that Pell's Equation won't be on the exam; does this mean that nothing from chapters 30-32 from the textbook is going to be on the exam? Also, just to confirm, since the midterm we have covered chapters 23-27, 33, and 34 - is this correct?

Q: How can we find that
x^25 = 1 mod 11, x /= 1 mod 11 and x^25 = 1 mod 43, x /= 1 mod 43 each of these congruences has 4 soultions

Q: What is Unique Factorization in Gaussian Integers?

A: This analogue of Fundamental Theorem of Arithmetic, but for Gaussian integers.
A Gaussian integer p is called prime if whenever p | ab then p|a or p|b.
Now unique factorization for Gaussian integers says that given any Gaussian integer N can be factored into primes. For example in Gaussian integers 2=(1-i)(1+i)

Q: prove the only integral solution to y^2 = x^3 + x is x = 0 and y = 0

A: suppose x^3 + x = y^2 now note x^3 + x = x( x^2 + 1) then note that x and x^2 + 1 are relatively prime and so x^2 + 1 and x are squares since the product is a square.

let k^2 = x^2 +1 then k^2 - x^2 = (k - x)(k + x) = 1 hence by the fundamental theorem of arithmetic in the integers k - x = 1 and k + x = 1 or k - x = - 1 and k + x = -1 and so k = 1 or -1 hence k^2 = 1 and so x = 0 and y = 0

Q: could someone help out with this: x^3 + 4x + 8=0 mod 15? thanks!

A: there are no solutions breaking up 15 = 5(3) check mod 3 x^3 + 4x + 8 = 0 mod 3 here the equation has no solutions in mod 3 and so has no solutions in mod 15.

(Why Not?) let x=2, the 2^3 + 4*2 + 8 = 8 + 8 + 8 = 24 = 0 (mod 3), so by CRT, it does not matter what mod 5 is, you can get a solution 0 mod15.

Q: What is Sum of two Square Theorem?

A: the sum of 2 squares theorem for prime numbers states if p is a prime then p can be written as the sum of 2 squares ie ( p = a^2 + b^2 ) for a , b integers iff p = 1 mod 4.

Q: What is Unique Factorization in Gaussian Integers?

Q:

5cdot 5 = (3+4i)(3-4i)

Why doesn't this equality contradict uniqueness of factorization to prime factors in Gaussian integers?

A: (assuming we are looking for integer solutions) This factors as (x+3y)(x-3y) = 1, and since we are looking for integer x and y, the factors x+3y and x-3y must also be integers. Then by factoring 1, we must have x+3y = 1 and x-3y = 1, or x+3y = -1 and x-3y = -1. In both cases, we find y = 0, and either x = 1 or x = -1. So the two integer solutions are (1,0) and (-1,0).

Q:
Find all the solutions of the equation

x^2-5y^2=1

A: This is a standard Pell's equation. See theorem 32.1 in the textbook. In this case D=5. The procedure for solving such equations is as follows: first find the solution (x_1, y_1) with smallest x_1 by continued fractions (theorem 40.4 in the textbook). Then all the solutions are obtained by taking powers of (x_1, y_1).
sqrt(5)=[2,overbar(4)], (Proposition 40.1 for example). Then p/q=[2,4]=9/4. m=1 is even (for this question), so the desired smallest solution is (9,4). Q
Find infinitely many solutions of the equation

x^2-5y^2=11

(there is no need to find all the solutions)

A: Take a look at exercise 32.1(d) in the textbook. It tells us that one can obtain the solutions to x^2-Dy^2=M (*) by first finding one particular solution to (*) and then combining it with solutions of x^2-Dy^2=1 in a certain way. One particular solution to x^2-5y^2=11 is (4,1) for example.

Q
Factor the Gaussian integer 5+15i into a product of non-unit Gaussian integers which can't be further factored as products of
non-unit Gaussian integers.
A:
5 + 15i = (1 - i)*(1 - 2i)^2 (1 + 2i)

Q:
a) Suppose that N(z)=p^2 for a Gaussian integer z and a prime number p. Show that if p=4k+3, then z is a Gaussian prime. Show that if p=4k+1, then z is not a Gaussian prime.

A:
a)

suppose N(z) = p^2 and let p = 3 mod 4 such that z is not guassian prime then z has nontrivial factorization say z= (a+ib)(c + id) WLOG
then N(z) = (a^2 + b^2)(c^2 + d^2) = p^2

hence a^2 + b^2 = p and c^2 + d^2 = p and so p is a sum of 2 squares but p = 3 mod 4 and from the sum of two squares theorem p cannot be written as the sum of two squares

so z has trivial factorization hence z is guassian prime.

suppose p = 4k + 1 and let z be a guassian prime then conjugate of z is guassian prime and the product of z * (conjugate of z ) is the product of 2 guassian primes.
but N(z) = z * (zbar) = p^2 and since p = 1 mod 4 then p can be written as the sum of 2 squares and hence p is the product of 2 guassian primes and so p^2 is the product of 4
guassian primes contradiction.

NQ: (not a question, but) Proof that -1 is a norm in

that is, there is a solution to x^2+y^2 = -1 mod p.

There must exist some quadratic residue a^2 such that a^2+1 is a quadratic nonresidue modulo p (because if every QR + 1 is a QR, then since 1 is a QR, we must have 1,...,p-1 all QRs, contradicting the fact that there are only (p-1)/2 QRs). But since p = 3 mod 4, -1 is a quadratic nonresidue, so therefore -(a^2+1) is QNR x QNR = a quadratic residue (call it c^2). Thus

and so

as desired.

NA: Cool! (Yura)

Q: Use uniqueness of factorization in Gaussian integers to show that there are no integer solutions of x^3 = y^2 + 1 with odd y.

A: What I meant was "with y even".

With y odd, the right side of the equation is 2 mod 4 and the left side of the equation is 0 mod 4.

So assume y is even.

Factor the right side of the equation as (y-i)(y+i). Now

Let's check whether y+i is divisible by 1+i:

Since y is even, this shows that y+i is not divisible by 1+i. Thus y-i, y+i are coprime.

Hence

for some units u,v. (Indeed, if x^3=mn with m,n relatively prime, then every prime factor of m appears with an exponent divisible by 3. Similarly for n).

Now let s=a+ib so that

Then

In particular comparing the imaginary parts we find that

i.e.

In particular either a or b is equal to plus/minus 1, while the other one is equal to 0. Thus s=a+ib is a unit, and hence y+i=u s^3 is a unit.

This is only possible for y=0, so we find the only solution x=1,y=0.

Q: how many solutions to the equation x^2 + y^2 ≡ 1 mod p

A: If -1 is a quadratic residue modulo p, then we can solve the question as follows:

Let a be such that a^2=-1. Then

Make an invertible change of variables:

(the inverse transformation is given by

)
Then the equation becomes zw≡1 mod p and hence has p-1 solutions (for every non-zero z there is a unique w with zw=1 mod p).

If -1 is not a quadratic residue, the solution above fails.

In this case we can obtain a different solution using a trick with parametrization of the circle we used when discussing pythagorean triples:

If (x_0,y_0) is a solution of x^2+y^2=1 mod p different than (1,0), then the "line" through (1,0),(x_0,y_0) intersects x^2+y^2=1 mod p in two points. Indeed, the system of equations

has at most two solutions because it can be reduced to a quadratic equation modulo a prime number, and it definitely has two solutions ((1.0),(x_0,y_0)).

Conversely, if m is any residue modulo p such that

then the system

has two solutions: (1,0) and

Thus any residue m whose square is not -1 produces a solution and every solution besides (1,0) is obtained this way. Thus if -1 is not a quadratic residue mod p, there are p+1 solutions (p solutions corresponding to different values of m and the solution (1,0)).

So the completeanswer is as follows: if p=2, there are 2 solutions. If p=4k+1, there are p-1 solutions. If p=4k+3, there are p+1 solutions.

Q:
how many guassian primes are there of norm less than 11

A:
there are no guassian primes of norm 0,1,3,4,6,7,8 or 10

the guassian primes of norm 2 are the following
1 + i , 1 - i , -1 - i , -1 + i

the guassian primes of norm 5 are the following
1 + 2i , 1 - 2i , -1 -2i , -1 + 2i , 2 + i , 2 -i , -2 - i , -2 + i

the guassian primes of norm 9 are 3, -3, 3i, -3i

hence there are 16 guassian primes of norm less than 11.

Q:
suppose p is prime integer such that p = mn where m and n are guassian integers and are not units prove conjugate of m is equal to n.

A:
suppose p is prime integer such that p = mn where m and n are not units and m = a+ ib then N(p) = N(m)* N(n) = p^2
hence N(m) divides p^2. Now since m is not a unit N(m) is not equal to 1 and so N(m) = p and so a^2 + b^2 = p
and so m* (conjugate m) = p.
but p = mn and so (conjugate of m) = n

Q:
a Gaussian integer is a Gaussian prime if and only if N(z) is a prime or a square of a prime of the form p=4k+3.

A:
suppose N(z) is prime and z is not a guassian prime then z has a nontrivial factorization hence there is a guassian integer m which divides z
hence N(m) divides N(z) contradiction since N(z) is prime.

suppose z is a guassian prime now if z is an integer z cannot be equal to 2 or congruent to 1 mod 4 since it would then be of the form a^2 + b^2 and would be divisible
by a + ib.

If z is not an integer then z divides a product of primes in the integers. Then since z*(conjugate z ) = N(z) by the unique factorization in guassian integers z divides a
prime integer say p. Hence N(z) divides N(p) = p^2 and so N(z) = p hence N(z) is prime.
(this is what i think Anthony)

For the other part
suppose N(z) = p^2 where p = 3 mod 4 and suppose z is not a guassian prime then z has a nontrivial factorization say z = (a+ ib)( c + di) where neither of the
factors are units. N(z) = (a^2 + b^2)(c^2 + d^2) = p^2 and so a^2 + b^2 = p and c^2 + d^2 = p which implies p can be written as the sum of 2 squares contradiction
by the sum of two squares theorem.

Q:
If z is a guassian prime then N(z) is a square of a prime p where p is congruent to 3 mod 4

A: This is wrong: 2+i is a Gaussian prime of norm 5.

Q:
Are there other solutions to q and r for which a=b(q) + r where a=48 + 27i and b = 1+2i and for which N(r) < N(b). Say, is r = 2 a valid solution?

A: Yes, the solution is not unique. Even in usual integers 5=2*2+1=2*3-1, so you have two choices for the remainder.

Q:
How many Gaussian integers are there of norm 120?

A: Since 120=2^3 3^1 5^1, and the prime 3 (which is congruent to 3 modulo 4) appears to an odd degree, there are no such Gaussian integers.

Q:
Factor the number 7! as a product of Gaussian primes A:

First factor it as a product of usual primes:

Now factor these primes as products of Gaussian primes:

Q:
let N(z) = p^2 where p is prime and z is a guassian integer if p = 3 mod 4 then z is a guassian prime

A:
suppose N(z) = p^2 and let p = 3 mod 4 such that z is not guassian prime then z has nontrivial factorization say z= (a+ib)(c + id)
then N(z) = (a^2 + b^2)(c^2 + d^2) = p^2

hence a^2 + b^2 = p and c^2 + d^2 = p and so p is a sum of 2 squares but p = 3 mod 4 and from the sum of two squares theorem p cannot be written as the sum of two squares

so z has trivial factorization hence z is guassian prime.
(this is what i think Anthony)

Another solution: If

and p is congruent to 3 mod 4, then the factorization of

to Gaussian primes is p^2. Hence z=u p for a unit u. Hence z is a Gaussian prime.

Q:
if p =1 mod 4 and N(z) = p^2 then z is not a Guassian prime

A: If p=1 mod 4, then p is a product of 2 Gaussian primes. Hence p^2 is a product of 4 Gaussian primes.

If z is Gaussian prime, then the conjugate of z is Gaussian prime and hence

is a product of 2 Gaussian primes.

Thus if p =1 mod 4 and N(z) = p^2 then z is not a Guassian prime

Q:
find Guassian integers q and r for which a=b(q) + r where a=48 + 27i and b = 1+2i and for which N(r) < N(b)

N(r) = 2 < 5
hence
the guassian integers q and r are the following
q = 21 - 14i
r = -1 - i

Q:
When is -7 a square mod P?

A:
For p which is not 2 and not 7

Thus it is 1 if and only if p is congruent to 1, 2 or 4 modulo 7.

Q:
Compute

A:
(-32/101) = (-1/101) * (2/101)^5
now (2/101) = -1 since 101 is congruent to 3 mod 8
and (-1/101) = 1 hence (-32/101) = -1

Q:For what primes p the number 5 is a quadratic residue?

Is p=2 a solution as well?

A:
Yes, 5=1^1 mod 2.

Q:
How many quadratic residues are there modulo 31? why is the answer (31-1)/2?

A:
There are 31 possible residues modulo 31: numbers from 0 to 30 represent all of them. Excluding 0 half the values are quadratic residues and half are quadratic non residues hence
the number of quadratic residues is (31-1)/2

Q: If

p=2^k+1

is prime, show that 3 is not a quadratic residue.

Combine this with the result of question 2 from March 1 to conclude that every number not divisible by p is congruent to a power of 3 modulo p.

A: To show that 3 is not a QR, that means (3/p)=-1
based on the formula, (p-1)/2 is even, (3-1)/2=1 and "(p/3)=1 iff p=1". so (p/3)= -1 for sure
then we show that 3 is not a QR.
From March 1st, we know that "a is a quadratic non-residue modulo p if and only if a is a primitive root modulo p" Then we can say 3 is a primitive root mod p and by primitive element thm, every number which is not divisible by p is of the from 3^i for an unique "i" from 0 to p-1. (This is what I think, Kevin Chen)

Q: Why are odd powers of primitive roots exactly the QNR?

A: Let a be a primitive root modulo p. If the number x is a QR, then x=n^2 mod p. If n=a^i mod p, then x=a^(2i) mod p. Thus every QR is an even power of a. Conversely, even powers of a are clearly QR. Thus the remaining (odd) powers of a are the QNR.

Q：

A:

Now (2/101)=-1 because 101=-3 mod 8

Hence
(14/101)=1

Q: Find infinitely many solutions of the equation
x^2 - 5 y^2 = 11 (there is no need to find all the solutions)

How to solve such questions with RHS not equal to 1?

A: One solution is x=4,y=1.

Let now

(see solution of the question below for explanation of what is special about 9+4sqrt(5) )

Then x_k^2-5 y_k^2 = 11.

I am not really sure how to find all possible solutions of this equation.

Q: find the integer solutions to x^2-5y^2 = 1

A:
the integer solutions
the smallest positive integer solution where x and y is greater than zero is x=9 y=4
hence the other positive integer solutions are (x_k,y_k) such that

for integer non-negative k.

Q: Which lectures/questions will quiz 3 cover?

A: Now posted on the main page.

Q: Let p = 2^n + 1 be a prime (n > 0). Show that a is a quadratic non-residue modulo p if and only if a is a primitive root modulo p. The answer below says: "Let c be any primitive root modulo p. Then the other primitive roots are c^i with i relatively prime to p-1. In our case this means c is relatively prime to 2^n, which is the same as saying that c is odd. But odd powers of a primitive root are exactly the quadratic non-residues."
Is this showing both directions of the if and only if?

A:
Yes: the odd powers of a given primitive root c coincide with both sets: the set of quadratic non-residues and the set of primitive roots mod p. Hence these two sets are the same.

Q: Show that any prime number p which is congruent to 1 modulo 6 is a divisor of some number of the form

n^2+3

A:
let p be any prime
suppose p=1 mod 6. Notice that p is an odd prime. Now we want to show -3 is
a square mod p.
(-3/p) = (-1/p)(3/p)
= (-1/p)(-1)^(p-1)/2*(3-1)/2 (p/3)
= (p/3) since p is odd.
now since p=1 mod 6 we also have p=1 mod 3, hence (p/3)=1

hence (-3/p)=1, i.e. -3 is a square mod p. Thus n^2 = -3 mod p for some integer n hence p divides a number of the form n^2 +3.

Q: how many solutions are there to x^2- 9y^2 =1

A:
Integer solutions:
(x-3y)(x+3)=1
Hence x-3y = 1, x+3y=1 or x-3y= - 1, x+3y= -1. Hence x=1 or -1, y=0. There are two integer solutions.

(in rationals there are infinitely many solutions).

Q: If

p=2^k+1

is prime, show that 3 is not a quadratic residue. Combine this (question 2 March 6) with the result of question 2 from March 1 to conclude that every number not divisible by p is congruent to a power of 3 modulo p.

See below
By the question from March 1 this means that 3 is a primitive root modulo p. Thus every non-zero residue modulo p is a power of 3.

Q: For what primes p the number 5 is a quadratic residue?

A:
For p different from 5,

The quadratic residues modulo 5 are 1 and -1. Hence the answer is

Q: What are all the quadratic residues modulo 19.

A:

Hence quadratic residues are 1,4,5,6,7,9,-8,-3,-2.

Q: How many quadratic residues are there modulo 31?

A: (31-1)/2=15

Q: Show that the congruence
has a solution modulo any prime.

A:
let p be any prime
Here if x^2=-1 mod p or x^2=-2 mod p has a solution then -1 or -2 is a quadratic residue mod p.
if neither -2 or -1 is a quadratic residue then they are quadratic non residues. But (-2)(-1) = 2 is a product
of quadratic non residues and hence is a quadratic residue hence x^2= 2 mod p has a solution and so
(x^2+1)(x^2+2)(x^2-2) =0 mod p has a solution.

Q: Let a be a quadratic residue mod p and let p be an odd prime
prove a is not a primitive root mod p

A:
Suppose a is a quadratic residue mod p.
Since p is an odd prime and a is a quadratic residue, a^(p-1)/2 is congruent to 1 mod p by Euler's criterion.

This means that the order a is at most (p-1)/2, so a is not a primitive root.

Q: Let a be a quadratic residue mod p and let p be an odd prime the integer p-a is a quadratic residue mod p if p=1 mod 4
and is a quadratic non residue if p=3 mod4

A:
suppose p is an odd prime and a is a quadratic residue mod p.

now (-1)^(p-1)/2 is equal to 1 when (p-1)/2 is even hence p-1 = 4k for some integer k and so p=1 mod4

(-1)^(p-1)/2 is equal to -1 mod p when (p-1)/2 is odd hence p-1= 4j +2 hence p=3 mod 4

Q: If p = 2^k + 1 is prime, show that 3 is not a quadratic residue.
Combine this with the result of question 2 from March 1 to conclude that every number not divisible by p is congruent to a power of 3 modulo p.

A:

If k>1 and k is even, then this number is equal to

so 3 is a quadratic non-residue modulo p.

If k=1, then p=3 and the question doesn't make sense.

If k is odd, then 2^k+1 = (-1)^k + 1 = 0 mod 3 and hence p is not prime.

Q: Let p = 2^n + 1 be a prime (n > 0). Show that a is a quadratic non-residue modulo p if and only if a is a primitive root modulo p.

A: Let c be any primitive root modulo p. Then the other primitive roots are c^i with i relatively prime to p-1. In our case this means c is relatively prime to 2^n, which is the same as saying that c is odd. But odd powers of a primitive root are exactly the quadratic non-residues.

Q: Show that 4 is not a primitive root modulo any prime p.

my attempt:
Artin's conjecture: 2 is a primitive root modulo for infinitely many primes
if p odd:
then all primitive elements of p is in the form of 2^i, gcd(i,p-1)=1
2^2=4, gcd(2,p-1)=2 for all, thus 4 cannot be a primitive root modulo of any prime
if p=2,
4=0mod2; not a primitive root

is this correct?

A: no!
1) Artin's conjecture is still not proved.
2) It doesn't apply to all primes, only to infinitely many primes.

A solution has been posted below.

Q:
how many primitive roots mod 19 exist? express them in powers of 2, 2 is one primitive root.

i tried phi(18) = 6, so there are six roots. 2 is given as one of them. will 5 7 11 13 17 be other roots since they are relatively prime to 18?

A: 2^5, 2^7, 2^11, 2^13, 2^17 are the other primitive roots

Q:Solve the congruence x^2+x-1 = 0 mod 1
A: Complete the square:

Square roots of 4 modulo 11 are + or - 2. Thus x=-6 -2 = -8 = 3 or x=-6+2=-4 mod 11
1

Q: In the 2009 past midterm, question 1(b): "find all solutions to x^3 + 4x + 8 = 0 (mod 15)." We should start by looking at the same congruence mod 3 and mod 5, but how do you handle polynomials like this (especially since we can't factor or use our quadratic equation tricks)?

A: 3 and 5 are very small numbers: just try all the possibilities. Small tricks: x^3=x for all x by FLT, so x^3+4x+8 = x+4x+8=2x+2 mod 3, so x=-1 mod 3.
x^3+4x+8=x^3-x-2=0 mod 5. x=-2,-1,0,1 ro 2 don't work, so there seem to be no solutions to this congruence.

Q: In class we said that CRT produces a unique solution, although at the same time we are using it as a tool to show that there are multiple possible solutions (eg, question1 quiz 2 and the question answered below 'How many solutions does the congruence 1+x+...+x^23 = 0 (mod111) have?'). Can you please clarify how we are using CRT in these cases.

A: CRT guarantees that there exists only one solution modulo mn to a congruence of the form x=a mod m, x=b mod n if m and n are distinct.

If f is a polynomial, m,n are relatively prime and we try to solve f(x)=0 mod mn, then we can solve f(x)=0 mod m and f(x)=0 mod n. By CRT for each solution of f(x)=0 mod m and for each solution of f(x)=0 mod n we get a solution of f(x)=0 mod mn. Thus if the first congruence has r solutions and the second one has t solutions, then the congruence f(x)=0 mod mn has rt solutions.

Q : Could you provide the full procedure of finding the solutions of x^3 = 8 mod 13 ?

Q：How many elements of order 6 are there modulo 13? List them all. my attempt: you look at all the elements co-prime to 13..from 1 to a12 and check which one raised to 6 gives 1mod13. my answer:1,3,4,9,11 and 12..please verify

A: 4 and 10 are the only elements of order 6 mod 13. This question is answered below.

Q: How many elements of order 5 are there modulo 13? using the same method, i only got one element: 1..

A: First of all, 1 doesn't have order 5, it has order 1 (order is the LEAST power you need to raise it to to get 1.) So in this case, there are no elements of order 5 modulo 13. We proved in class that elements of order k exist only if k divides phi(n). In this case n is 13, phi(13) is 12, so you will only get elements of order 1, 2, 3, 4, 6, or 12. None of order 5.

Q:How many irrational solutions x does the equation x^3 - 5x + 2 = 0 have? Find them explicitly.

A:First try to find rational solutions, which is 2. Use the thm we learned on Jan. 12th," If x=m/n, (m, n coprime) is a root of a polynomial a0x^k+a1x^(k-1)+...+ak=0, then m|ak, n|a0."
Then we kan get (x-2)(x^2+2x-1)=0 and solve x^2+2x-1=0. We get two irrational answers. (That is what I think, I am Kevin Chen :P) Thank you once again Kevin!

Q: Decide whether the equation x^2 - y^2 = 2 has zero, finitely many or infinitely many rational solutions x,y. Justify your answer. A: One way to solve this question would be to factor the left-hand side, to get (x+y)(x-y)=2. So write 2 as a product of two rationals a and b, with x+y=a and x-y=b.
Now given any system of equations
x + y = a
x - y = b
we can add or subtract the equations to get solutions
x = (a + b)/2
y = (a - b)/2
so for every possible way to write 2=ab, with rational a, b, we get rational x and y. There are infinitely many pairs a, b (let a be any nonzero rational number, and b = 2/a), so there are infinitely many solutions x, y.
(for example, 3*(2/3) = 2, so let a=3 and b=2/3. Then x = 11/6 and y = 7/6, and (11/6)^2 - (7/6)^2 = 2.

Q: Quiz2.2.2
Solve the congruence
x = 3 mod 35
x = 2 mod 15
A: we can get x=35a+3 and x=15b+2, then 35a+3=15b+2 i.e 15b-35a=1. Since gcd(35, 15)=5, not 1, so there is no sol'n for "a" and "b". Hence, no such x.
(That is what I think, I am Kevin Chen :P) Thank you very much, Kevin! (Yuri)

Q: Show that if

2^n-1

is prime, then

n|2^n-2

Hint: order of an element modulo a prime p divides p-1 A: Order of the number 2 modulo 2^n-1 is obviously n. Thus n divides (2^n-1)-1 if 2^n-1 is prime. Longer answer: Math @ Stack Exchange

Q: Give a characterization of primes p for which the congruence

x^4 + 1 equiv 0 mod p

has at least one solution.

A: This was answered below.

Q: How many elements of order 6 are there modulo 13? List them all. I got the answer to be 3 elements: 4,10,12 but by checking all numbers. Is there any other way which is less tedious?

A: First of all, 12 is not order 6, it's order 2. So there are only two elements: 4 and 10. Once you've found one element, you can find the others pretty easily. So let's say you've checked and found that 4 is order 6. This means 4^6 = 1 mod 13. Then all other elements of order 6 will be some power of 4 - not 4^2 (because (4^2)^3 = 4^6 = 1 mod 13, so it has order 3), not 4^3 (it has order 2), not 4^4 (has order 3), but 4^5 is fine. Basically - any number relatively prime to 6 (1 or 5) will give you an exponent that will give you another remainder mod 13 of order 6. Say, for another example, you want to find elements of order 10 modulo 31. You find 15 works. Then 15^1, 15^3, 15^7, and 15^9 will give you all elements of order 10 mod 31.

Q: How many polynomials

x^k+a_1x^{k-1}+ldots+a_k

of degree k with coefficients 0 and 1 don't have exactly two roots?

Can such a polynomial have more than two roots?

A: The polynomial can't have more than two roots (there are only two residues, 0 and 1, modulo 2).

As for the number of polynomials f with exactly two roots, the condition is f(0)=0 and f(1)=0. This translates to conditions a_k=0, 1+a_1+...+a_k=0, giving a total of 2^{k-2} polynomials.

Q: Professor, for the midterm, should we expect questions similar to the format which we've been exposed to on our quizzes (suggested problems, etc.), or should we prepare ourselves for proofs, and questions of this nature? Thanks for your time! A: There are three questions that start with "show ..." But these are questions of the same format that appeared in suggested problems (e.g. "show that if p>3 is a divisor of n^2+n+1 then p-1 is divisible by 3").

Q: Could you please post the solutions to the quizzes? I know some of the answers are below, but there are a few missing. Thanks!
A: No, sorry. If you are not certain about one of the quesions, please ask here.

Q: For the midterm, it states that material up to primitive element theorem and its applications will be tested. However, does that mean material up to and including the primitive element theorem and its applications, or does that mean only up to?

A: The test includes questions on primitive element theorem, order of an element and applications of primitive element theorem

Q: Give a characterization of primes p for which the congruence x^4 + 1 = 0 mod p has at least one solution.

A: If x^4=-1 mod p then x^8=1 mod p, so order of x is a divisor of 8, i.e. it is 1, 2, 4 or 8. But x or x^2 or x^4 =1 mod p contradicts x^4=-1 mod p, so order of x is 8. Thus 8|p-1.

Conversely, if 8|p-1, then let y be a primitive root mod p and let x=y^{(p-1)/8}. Then z=x^4=y^{(p-1)/2}= -1 mod p (because z^2=1 mod p, but z is not 1).

Thus the characterization is "those primes p for which p-1 is divisible by 8".

Q: Solve the congruence x^3 = 8 mod 13^3

A: x^3=8 mod 13 has 3 solutions: x=2, x=6, x=5 mod 13.

Consider first the case of x=2 mod 13.

Let x= 2 + 13 y. Then

So we want to solve

or equivalently

This means that y=0 mod 13, i.e. y=13z. This translates to

so z=0 mod 13.

Thus we get a solution x=2 mod 13^3.

Consider now the case x=6 mod 13. Let x=6+13 y. Then we want to solve

(the term with 13^3y^3 is not included, because it is zero modulo 13^3)

or equivalently

or

Since 16+3*36y=0 mod 13, this means 3-9y=0 mod 13 or y=-4 mod 13. Let y=-4+13z and get

or equivalently

or

so z=1 mod 13.

Finally x=6+13*(-4+13(1)) mod 13^3, i.e. x=123 mod 13^3

The case x=5 mod 13 can be considered in a similar fashion.

Q: (repost) Show that every prime divisor p>3 of n^2 + n + 1 is congruent to 1 modulo 6

A: Let's compute the order of n modulo p.

If n=1, then n^2+n+1=3 and p=1 or 3, contradicting p>3.

So n is not 1.

If n^2=1 mod p, then p divides n^2-1=(n-1)(n+1). Hence n=1 or -1 mod p, and hence n^2+n+1=3 or 1 mod p, contradicting that n^n+n+1=0 mod p.

Finally n^3=n(n^2)=n(-1-n)=-n-n^2=1 mod p (we are using here that 1+n+n^2=0 mod p). Thus order of n mod p is 3 and hence 3 divides p-1.

Since p is also odd, it means that p=1 mod 6.

Q: Find all solutions of x^42 = 4 (mod 100)

A: x^ 42=4 mod 100 if and only if x^42=4 mod 4 and x^42 = 4 mod 25.

For the first congruence x^42=0 mod 4 the solutions are x=0 or 2 mod 4, i.e. x=0 mod 2.

For the second congruence notice that x must be relatively prime to 25, so x^20=1 mod 25 by Euler's theorem. Thus the equation x^42=4 mod 25 is equivalent to x^2=4 mod 25, i.e. 25|x^2-4=(x-2)(x+2). Since (x-2) and (x+2) can't be simultaneously divisible by 5, this means that 25|x-2 or 25|x+2. Thus x=2 or -2 mod 25.

Finally combine this with x=0 mod 2 to get the answer x=2 or -2 mod 50 (equivalently x=2, -2, 48, 52 mod 100)

Q: For this problem: x^3 = 8 (mod13^3). I started by trying to solve x^3 = 8 (mod 13) and got x = 2,5,6 (mod13).
From here, I used the method shown in class for each of x = 2,5,6 to arrive at 3 solutions for x^3 = 8 (mod13^3).
Namely, x = 2, -125, 123 (mod 13^3).
Is this the only method of doing the question, or are there any less "tedious" ways?

A: This is the right method. Unfortunately I am not aware of a less tedious method.

Q: Show that every prime divisor p>3 of n^2 + n + 1 is congruent to 1 modulo 6

A: Hint: To show that p-1 is divisible by 3, show that the order of n modulo p is 3. Let me know if you need a more complete answer by reposting this question on the top.

Q: How many polynomials

of degree k with coefficients 0 and 1 don't have any roots modulo 2?

A: The condition is that f(0)=1, f(1)=1 mod 2. The first condition is equivalent to a_k=0 mod 2. The second condition is equivalent to a_1+a_2+...+a_k=0 mod 2. Thus we can choose a_1,...,a_{k-2} in an arbitrary manner and a_{k-1} mod 2 is determined, while a_k=0 mod 2. Thus there are 2^{k-2} such polynomials.

Q: How many solutions does the congruence 1+x+...+x^23 = 0 (mod111) have?

A: Since 111=3x37, the congruence 1+x+...+x^23=0 mod 111 is equivalent to the system of two congruences 1+x+...+x^23=0 mod 3 and
1+x+...+x^23=0 mod 37.

The first of these has 2 solutions x=1 or -1 mod 3 (just try 0, 1 and -1).

For the second equation, notice that 1+x+...+x^23=0 mod 37 is equivalent to (1-x)(1+x+...+x^23)=1-x^24=0 mod 37 and x is not congruent to 1 mod 37. The number of solutions of x^24=1 mod 37 is gcd(24,36)=12. Since x=1 is one of the solutions and we want to exclude it, we get 11 solutions of 1+x+...+x^23=0 mod 37.

By CRT we get 2x11=22 solutions for the original congruence modulo 111.

Q:
find all solutions to x^7 is congruent to 15 mod 137

A: 136=8*17, so 7 is invertible modulo 136. Find the inverse s and the answer is 15^s mod 137.

(s=39, 15^39=121 mod 137)

Q:
find all solutions to x^17 is congruent to 0 mod 137

A: 137 is prime, so 137|x^17 if and only if 137|x.

Q:
if 2^n-1 is prime prove n divides 2^n-2

A: For k<n, 2^k<2^n-1.
Since

this shows that order of 2 mod 2^n-1 is exactly n. Thus n divides (2^n-1)-1=2^n-2.

Q:
Show that 4 is not a primitive root modulo any prime p.

A: If p is odd, then since 4=2^2,

and thus the order of 4 is smaller than p-1.

If p=2, then 4=0 mod 2 and hence is clearly not a primitive root.

Q: How many solutions does x^51 = 1 (mod 137) have.
Note: I solved that x^17 = 1 (mod 137) has 17 solutions. Hence
x^51 = 1 (mod 137) must have at least 17 solutions as well. I am trying to use the fact that there is no x with order 51 to prove that every x st
x^51 = 1 (mod 137) must also satisfy x^17 = 1 (mod 137), hence if this holds then that means it will also have 17 solutions.
Is this the correct approach? Please provide some clues, thank you!

A:
You could do it that way indeed: if x^51=1 mod 137, the order of x mush divide both 51 and 136, hence it must be 1 or 17. In any case x^17=1 mod 137. Conversely if x^17=1 mod 137, then x^51=1 mod 137.

An alternative way: if x^51=1 mod 137, then x^17=1^s=1 mod 137 where s is the inverse of 3 mod 137.

has 17 solutions and then for each solution y the congruence

has only one solution

(because 3x91 = 1 mod 136)

Q: In class we covered the problem x^2 + ax+ b = 0 (mod p). Could you re-explain this example with emphasis on
(i) Why you divided the cases into p=2 and p does not equal 2
(ii) The case when p=2, it suffices to solve x^2 = 0, x^2 + x =0, x^2+1 =0, x^2+x+1=0.

A: (i) The trick with completing the square, or, equivalently, the formula

works only if we can divide by 2. If p is equal to 2, we can't do it, so we have to consider p=2 separately.

(ii) If p=2, the coefficients a, b could only be 0 or 1 mod p. Thus there are only 4 equations to solve and each one of them is easily solvable.

Q: Could you please provide a list of which chapters from the textbook we have covered? Thanks！

A: We covered 1,2,3,5,6,8,9,10,11,12,16,17,18,19,20,21,22,part of 23,part of 24

Q: From the question that was solved below

The solution was x = 3. Why do we not include x = 3 * (k * 7 + 1), k>=1 as other solutions to the congruence?

A: The answer is

which is equivalent to saying x=3+21 k for any integer k.

Q： How many solutions does the congruence x^40= 1 (mod100) have?

A: Since x^40=100m+1, it means that gcd(x,100)=1 (because 1 is divisible by gcd(x,100)).
If x is relatively prime to 100, then x^{\phi(100)}=1 (mod 100). \phi (100)= (4-2)(25-5)=40.
So x is the solution of x^40=1(mod 100) if and only if x is relatively prime to 100.
There exactly \phi(100)=40 distinct (modulo 100) numbers that are relatively prime to 100. Answer:The congruence has 40 solutions

Q: N=pq, where p and q are distinct primes. there exist x and y, such that x*2=y*2 mod N, but x is not congruent to y mod N, and x is not congruent to -y mod N. find p and q.

A: It's impossible to determine p and q: one can have x=y mod p and x=-y mod q for any distinct p and q.

Q:How many solutions does the congruence x^40 is congruent to 2 mod100 have A: This congruence doesn't have a solution. If x^40=2 mod 100, then x is even, but then x^40 is divisible by 4 so can't be equal to 2 mod 100.

Q: I was wondering if you could provide the answers for 18.2 please.

18.2 (a) Show that in fact RSA decryption does work for all messages a, regardless of whether or not they have a common factor with m.
(b) More generally, show that RSA decryption works for all messages a as long as m is a product of distinct primes.
(c) Give an example with m=18 and a=3 where RSA decryption does not work (remember, k must be chosen relatively prime to phi(m)=6).

Parts (a) and (b) are similar to 17.4 which asks to show that b^u as found by Algorithm 17.1 is still a solution for "x^k is congruent to b mod m" if gcd(b,m)>1 but m is a product of distinct primes. u is a solution to ku-phi(m)v=1.

A: a,b) Let N=p_1p_2 ... p_n for distinct primes p_i

RSA algorithm starts with message a and outputs a^{ks} mod N where ks = 1 mod phi(N).

The message a could be divisible by p_i or not divisible by p_i. If it is, then a^{ks}=0=a mod p_i. If a is relatively prime to p_i, then a^phi(N)=1 mod p_i, since phi(N) is divisible by p_i - 1. In particular a^{ks}=a mod p_i. Thus regardless of what a is, a^{ks}=a mod p_i for all i and hence a^{ks}=a mod N by CRT.

Q: Feb 07:Solve the congruence x^2+x-1=0 mod 11 A: 11 is a prime number, so we can divide. x^2+x-1=(x+1/2)^2-5/4=0 (mod 11). 1/4=3 (mod 11), so (x+1/2)^2=4 (mod 11), so x+1/2=2 (mod 11) or x+1/2=-2 (mod 11). 1/2=6 (mod 11), so x=3 (mod 11) or x=7 (mod 11)

Q: general question about fermat: does p have to be necessarily prime?
consider: 7^5=1 mod6, 6 is not prime, only that 7 and 6 are co-prime. please advise, thx.

A: Fermat's little theorem guarantees that if p is prime, then a^(p-1)=1 mod p for all a not divisible by p. It doesn't say anything about whether for a composite number n the equality a^(n-1)=1 mod n holds for some particular values of a. In your example 7^5=1^5=1 mod 6, but the reason has nothing to do with FLT (it has to do with the fact that 1 raised to any power is still 1).

it cannot be sufficient to simply state that since 7*1734250 is not congruent to 1 modm, m is not prime?

A: If m is prime, then by FLT

Since this equality doesn't hold, m is not prime.

Q: Find a multiple of 77 that ends with 999

attempted:
77x=999mod1000 (subtracting 999 from that multiple would leave 3 0s)
but came up with x=12987; clearly wrong, please correct!

A: 12987*77=999999

Q: find the non-negative solutions of 7x+19y=1

A: if x>0 or y>0 then 7x+19y>1. If x=0 and y=0, then 7x+19y=0. Thus there are no non-negative solutions of this equation.

Q:
Show that the congruence
x^2 = a (mod21)
can have 0, 1, 2 or 4 solutions depending on a

I tried to show this by using CRT: since 21 is the product of 3 and 7, I worked with two congruences
(1): x^2=a(mod3) and
(2): x^2=a(mod7)
then showed that both congruences can have 0, 1 or 2 solutions (depending on a) (by solving for a= 0, 1, 2 for (1) and a = 0, 1, 2, ..., 6 for (2)), which
implied that (3): x^2=a(mod 3*7=21) has 0, 1, 2, or 4 solutions (depending on a) (since multiplying the number of solutions for (1) and (2) with the same value of a gives the number of solutions for (3)).
Is this correct or are there any less tedious methods?

A: This is correct.

We have recently learned a theorem that equation of degree n has at most n different roots modulo a prime p, which shows immediately that x^2=a mod 3 and x^2=a mod 7 each have 0,1 or 2 solutions, but without using it what you did is indeed the best way.

Q1 Find 2^220 (mod 221) Conclude that 221 is composite.

A: Use successive squaring:

2^220=4^110=16^55=16*256^27=16*35^27=16*35*1225^13=16*35*120^13=16*35*120*14400^6=16*35*120*35^6=16*35*120*120^3=16*35*120*120*35=16 mod 221

If 221 were prime, then 2^220 would have been 1 mod 221 by FLT. Hence 221 is composite.

Q2 Show that a^48=1 (mod 221) for all a relatively prime to 221.

A: 221=13*17

a^48=a^(12*4)=1 mod 13 by FLT
a^48=a^(16*3)=1 mod 17 by FLT
Thus a^48=1 mod 221 by CRT

Q:Solve the congruence
(*)
A: if x is the solution of (*) we have x^7=3(mod 7), x^7=0(mod 3) so 3|x.
y^6=1(mod 7) for all y that are coprime with 7. So (since our x is clearly coprime with 7)
x^7=x^6*x=x=3(mod 7). So x=0(mod 3) x=3 (mod 7) but chinese remainder theorem
the solution mod 21 is unique and 3 is clearly the solution.

Q: According to Feb 2 lecture, X^24 = 1 (mod 35) has phi(35) = 24 solutions. Why is this?

A: By the Euler theorem any x such that (x,m)=1 satisfies

So for m=35 phi(35)=(5-1)(7-1)=24 so any x that is coprime (and there exactly 24 such x mod 35) with 35 is a solution of x^24=1 (mod 35)
if x is not coprime with 35 then it can't be the solution because (1,35)=1.

A: We should solve
x=3+37k, x=1+87m, or, equivalently, 3+37k=1+87m, i.e. 87 m - 37 k = 2.

Rewrite this as 13m - 37 (k - 2m) = 2 and let k'=k-2m. Rewrite 13m - 37 k' = 2 as 13(m-3k') + 2 k' = 2. One solution is m-3k'=2, k' = - 12. Thus m= -34, k=k'+2m = -80.

Thus x=3+37 k = 3 - 37*80= - 2957.

(This is only one possible solution. Other ones are given by -2957 + 87*37 t with integer t).

Q: Show that for

the congruence

holds for every a relatively prime to m.
(Hint: use Fermat's little theorem to compute a^{m-1} mod p for every prime divisor p of m).

A: This was shown in class Tuesday, January 31.

Q: Find the remainder when a is divided by m (a) a=207^321+689! m=7

(b) a=(123)(45)(678)(910)(112) m=6

A: a) 689! is divisible by 7.
207=(-3) mod 7 and (-3)^6= 1 mod 7 by FLT. Thus 207^321 = (-3)^(53*6+3)= (-3)^3 = 1 mod 7.
b) 678 is divisible by 6, so the whole product is also divisible by 3.

Q: For the following two questions:
9.4 a) Assuming that the congruence

holds, show that 1734251 is a composite (i.e. non-prime) number.
c) The congruence

is true. Can you conclude that 52633 is a prime number?

Is it enough to just show by using Fermat's little theorem?

A: In a) FLT shows that 1734251 is composite.
In c) FLT doesn't show anything.

Q: 8.4 (d) Show that a number is divisible by 9 if and only if its sum of digits is divisible by 9.

A: Let the number be

i.e. the digits are a_0,a_1,...,a_n.

Then

This shows that the remainder of division of the number by 9 is the same as the remainder of division of its sum of digits by 9.

Q: based on 2.1 (b) Show that in a primitive Pythagorean triple a,b,c exactly one of a,b,c is divisible by 5.

A: Modulo 5 all the squares are congruent to 0 or plus/minus 1. If a^2+b^2=c^2 mod 5 and (a,b,c) is not (0,0,0) mod 5, the only options are

In each of these cases exactly one of a,b,c is equal to 0 mod 5.

Q :Find all integer solutions of the equation 65432 x + 98765 y = gcd(65432,98765)

A: 98765=65432+33333, so we rewrite this equation as 65432 x' + 33333 y = gcd (65432, 33333) with x'=x+y.

Next 65432 = 2*33333-1234, so we rewrite the equation as -1234 x' + 33333 y' = gcd ( -1234, 33333) where y' = y+2x'.

Next 33333 = (-27)*(-1234) + 15, so we rewrite the equation as -1234 x'' + 15 y' = gcd ( -1234, 15) where x''=x'-27y'

Next -1234 = (-82)(-15)-4, so we rewrite the equation as -4 x'' + 15 y'' = gcd(-4,15) where y''=y'-82x''

Finally 15 = (-4)(-4)-1, so we rewrite the equation as -4x''' - y'' = gcd(-4,-1)=1, with x'''=x''-4y''.

One solution of this equation is x'''=0, y''=-1, i.e. x''=-4, y'=y''+82x''=-329, x'=x''+27y'=-4+27*(-329)=-8887, y=y'-2x'=-329+2*8887=17445, x=x'-y=-8887-17445=-26332.

All other solutions are given by x=-26332 + 98765 k, y=17445 - 65432 k, k - any integer.

Q : Find 10^5^101 (mod 21)

A: 10=1 mod 3, so 10^5^101 is 1 mod 3.

By FLT, 10^6=1 mod 7. Now we want to divide the exponent 5^101 by 6 with remainder. We see immediately that 5^101=(-1)^101= -1=5 mod 6. Thus 10^(5^101)=10^(6q+5)=10^5 mod 7.
Finally 10^5=3^5=5 mod 7.

Combining these two results using CRT we find that 10^5^101=19 mod 21.

Q: Find a number

with

A: 73 is a prime number, so by FLT 9^72 = 1 mod 73. Now 794=11*72+2, so 9^794=9^2=81=8 mod 73

Q. Show that for a prime number p the number (p-1)!+1 is divisible by p
(Hint: consider the number (p-1)! mod p. In this product one can split most of the residues to pairs of a residue and its inverse).

A: In the product

every residue comes with its inverse modulo p. In general these two residues x and x^{-1} are different from each other, except when x=x^{-1}, or, equivalently, x^2=1, i.e x=1 or -1.

Thus (p-1)!= -1 mod p.

Q.
Does
x^10+y^10 = 11z^10
have non-zero solutions mod 6?

could it be shown using mod 6 instead of 4 from the answer below?

A: For a non-zero x, x^2=1,4,3 mod 6, so x^10=1,4,3 mod 6. Same holds for y^10. 11z^10 is 5,2,3 mod 6.
So 1^10+4^10=11*1^10 mod 6 is a non-zero solution mod 6.

So I don't see an obvious way of concluding non-existence of non-zero solution by trying to do it mod 6 instead of mod 4.

Q. Determine the value of 2^2012+3^3013(mod7)

A:
Compute first 2^2012 mod 7.
2^3=1 mod 7, so 2^2010=1^670=1 mod 7 and so 2^2012=4 mod 7.

Now 3^6=1 mod 7. Apply this to compute 3^3013 mod 7 in the same way: 3^3013=3^3012 * 3 =3 mod 7.

Thus 2^2012+3^3012 = 0 mod 7

Q:2.6) b) Find a Pythagorean triple (a,b,c) with c=a+2 and c>1000. c) Find all primitive Pythagorean triples (a,b,c) with c=a+2.

A: a^2+b^2=(a+2)^2 means 4a+4=b^2. This equation has a solution for every even number b: b=2k, a=k^2-1. If k is odd, a is even and the triple (a,b,a+2) is not primitive. However if k is even, then gcd(k^2-1,k)=gcd(-1,k)=1, so gcd(k^2-1,2k)=1 and thus the triple is primitive.
In short all the primitive solutions are of the form (k^2-1,2k,k^2+1) with even k.

Q: Solve

A:

So the solutions are 3 and -3 mod 7.

Q: Show that there are infinitely many primes of the for 6n+5.

A: First notice that every prime number, except 2 and 3 is congruent to either 1 or -1 mod 6.

Consider the number 6n!-1. All its divisors are at least n and among its prime divisor at least one must be congruent to -1 mod 6 (because the product is congruent to -1 mod 6).

Q: Show that the equation

has no non-zero integer solutions.

A:
We can assume gcd(x,y,z)=1
Let's look at the remainder of the both sides modulo 4.

so x^{10}+y^{10} mod 4 can be 0 (if they are both even), 1 or 2
11z^{10} mod 4 can be 0 (if z is even) or 3.
But
x^{10}+y^{10}=11z^{10}, so both sides are 0 mod 4 and x,y,z are all even,
that condradicts with the assumption gcd(x,y,z)=1.

Q: (2.3) Which odd numbers a can appear in a primitive Pythagorean triple (a,b,c)?

A: Any odd a can appear

Q: Which even numbers b can appear in a primitive Pythagorean triple (a,b,c)?

A:
If b is not divisible by 4 it cannot appear in the Pythagorean triple.
Let's look at the remainders of both sides modulo 8.
a, c are odd so their squares can be only 1 mod 8. If b is not divisible by 4
b^2 mod 8 is 4, so a^2+b^2 mod 8=5 that is not equal to one.
If b is divisible by 4 take b=2^{k}d, where d is odd. We know that k>1.
Then take the Pythagorean triple a=2^{2k-2} - d^{2}, b, c=2^{2k-2} + d^{2}.
Since k>1 a is odd.
gcd(a,b,c)=1 (assume the contrary, there exist prime p that divides a,b,c. Since a is odd p is odd. Odd prime p divides b, so it must divide d, so p must divide a+d^{2} that is a power of two. contradiction).
So we constructed a primitive Pythagorean triple with the given b.

Q: (2.1) We showed that in any primitive Pythagorean triple (a,b,c) either a or b is even. Use the same sort of argument to show that either a or b must be a multiple of 3.

A: Consider the identity a^2+b^2=c^2 mod 3. If neither a nor b are divisible by 3, then

and similarly for b^2. Thus a^2+b^2 = 2 mod 3, which is not a square of anything mod 3.

Thus either a or b must be divisible by 3.

Q: Show that the equation x^2 + x = y^2 has no non-zero integer solutions A:

Since x, (x+1) can't have common divisors if some prime p divides x, then p^2 divides x (since p divides y, so p^2 divides x(x+1) and gcd(x+1,x)=1). So

for some integer a. For the same reason

for some integer b. But it means that we got two plus/minus squares of integers with the difference one, so x=0 or x=-1.

Q: Show that if x, y,z have no common factors and satisfy the equation above (x^2 + 2y^2=z^2)
Then one can find integers s,t such that either z-x=2s^2, z+s=t^2 or z-x=s^2, z+x=2t^2.

A: First of all notice that x,z must be odd (if x is even, z is also even and it follows easily that y must be even as well).

Now rewrite the equation as 2y^2=x^2-z^2=(x-z)(x+z).

Notice that gcd(x-z,x+z)=gcd(x-z, 2x)=2gcd(x,z)=2.

Thus the only common factor of (x-z) and (x+z) is 2.

It follows that all the exponents of the primes other than 2 in the factorizations of x-z and x+z are even. The exponent of 2 is even in one of them and odd in the other one.

Thus either x-z=2s^2, x+z=t^2 or x+z=2s^2, x+z=t^2.

The required parametrization follows.

Q: Solve the equation x^2 + 2y^2=z^2 in integers.

A: See question above.

Q: (2.4)
In our list of examples are the two primitive Pythagorean triples

Find at least one more example of two primitive Pythagorean triples with the same value of c. Can you find three primitive Pythagorean triples with the same c? Can you find more than three?

A: I am sorry for assigning this question: it seems a bit tougher than I expected it to be.

One possible approach to it is to use the following identity:

(we will later learn how this identity naturally appears from some basic properties of complex numbers).

This identity allows you to get a representation of some numbers as sum of two squares in two different ways.

To get a representation of a number as a sum squares in four different ways, use this identity twice:

and now use the identity once again.

Q: Show that

for any natural numbers m,n.

A: We showed in class that if

then

Let's now divide n by m with remainder: n= qm+r. By applying the result above q times, we get that

So if we want to compute gcd(10^x-1,gcd^y-1), we can always replace the pair of parameters (x,y)=(n,m) by the pair (x,y)=(m,r) without changing the answer.

We know from what we have discussed about Euclid's algorithm that we can repeat this procedure until we get to the pair (gcd(m,n),0). For this pair the value of gcd(10^x-1,10^y-1) is

Q:Find an integer solution of

with a>1000 and with a, b, c having no common factor.

A: Let x=a/c, y=b/c. Then we want to find a rational solution x,y to the equation x^2+xy+y^2=3. One solution is x=1, y=1.

We showed in class that all rational solutions of such equation are given by intersecting the quadric with lines of the kind y-1 = m(x-1) with rational m. Plugging the value of y from the equation of the line into the equation of the quadric we find

One solution of this equation is x=1, so the second solution is

and

It remains to choose a large enough m so that the numerator and denominator in the fractions will be large enough, e.g. m=50 that gives a=2398, b= - 5099, c= 2551 (check that these are relatively prime!) .

Q: January 10 question1
Prove that

has no nonzero solutions

A: We can assume that gcd(m,n)=1, otherwise write

then

Now m_1 is divisible by three, so

is divisible by 9, so n_1 is divisible by three. We get the contradictionh with the fact that

Q: January 10 question4
Prove that if

and x,y,z have no common factors, then x and z must be odd and y must be even.

A: Assume x is even, then

is also even, so z is even and

is divisible by 4, so y is even and x,y,z have the common factor 2.
So x is odd and so is z (as a sum of odd and even number). Now if x,z are both odd then

is divisible by 4 and so y is even.

Q: January 10 question3
prove

has no solutions with x and y both odd

A: If x is odd, z must be odd as well. Let x=2k+1, y=2n+1, z=2m+1 the equation translates into 4k^2+4k+8n^2+8n+3=4m^2+4m+1. The left side gives remainder of 3 when divided by 4, while the right side gives remainder of 1. Thus no solution with odd x, y could possibly exist.

Q:
Show that

is irrational. (Hint:

A:

Applying the hint we find that

satisfies the equation

or, equivalently, 8x^3-6x-1=0. By a theorem we proved in class the only candidates for rational solutions of this equation are

By checking each one of these we find that the equation has no rational solutions, so x must be irrational.

Q: Find at least one integer solution to the equation 21x - 13 y = 1

A: Write the equation as 8 x + 13 (x-y) =1, let y'=x-y.
Now solve 8x + 13 y' = 1
Write it as 8 (x+y')+5 y' = 1
Let x'=x+y'
Solve 8x'+5y'=1
Write it as 3x'+5(x'+y')=1
Let y''=x'+y'
Solve 3x'+5y''=1
Write it as 3(x'+y'')+2y''=1
Let x''=x'+y''
Solve 3x''+2y''=1, or x''+2(x''+y'')=1.

One solution: x''=1, x''+y''=0, i.e. x''=1, y''=-1.
Now unwind the substitutions: x'=x''-y''=2
y'=y''-x'=-3
x=x'-y'=5
y=x-y'=8.

Thus one solution is x=5, y=8 (check: 21*5-13*8=105-104=1).

All other solutions are of the form x=5+13k, y=8+21k.

Q: Please provide some hints on how to do the second problem for January 10th:
Show that the equation x^2+x=y^2 has no non-zero integer solutions

Hint: If you want to show that something (x^2+x) is not a square of an integer, try to prove that it
can't fit into the "gap" between two consecuitive squares.

A hint to a different solution: rewrite the equation in the form

and use that x, x+1 are relatively prime.

Q: Show that if

is a rational number, then it is an integer.

A: If n=a^2/b^2 for some integers a, b, then nb^2=a^2. Let p be any prime number and let k_a, k_b, k_n denote the multiplicities of this prime in the prime factorizations of a, b, n respectively. The equality nb^2=a^2 and uniqueness of factorization to primes tells us then that k_n + 2 k_b = 2 k_a. Thus k_n is even.

Hence the prime number factorization of n is of the form

and hence square root of n is integer.
Introduction to Number Theory
Introduction to Number Theory

(\pm 1)^2,(\pm 2)^2, (\pm 3)^2,(\pm 4)^A,

Q: if n is an integer s.t n > 1 then n does not divide (2^n) - 1

A: suppose p is the smallest prime divisor of n in the factorization of n into distinct primes then gcd (n , p - 1) = 1 hence there are integers k and s such that n(s) + k(p - 1) = 1. now suppose p divides (2^n) - 1 then 2^n = 1 mod p and since p does not divide 2 then 2^( p - 1) = 1 mod p but 2 = 2^( n(s) + k( p - 1)) = (2^ n)(s)) ( 2^( p - 1)(k)) = 1 mod p contradiction hence p does not divide (2^n) - 1 and since p is the smallest divisor of n, n does not divide (2^n) - 1

Q: prove a^(2^n) = 1 mod 2^(n + 2) where a is odd

A: suppose a is odd then a = 2k + 1 k integer now 2^n = 2( 2^(n-1)) hence a^(2^n) = (a^2)(2^(n -1)). now 2^(n + 2) = 4(2^n) and a^2 = 4k^2 + 4k + 1 hence a^2 = 1 mod 2^(n + 2) a^2(2^(n - 1)) = 1^(2^(n - 1)) = 1 mod 2^( n + 2) hence a^(2^n) = a^2(2^( n - 1)) =1 mod 2^( n + 2)

how do you approach a question like 3x^2 + 5x +1=0 mod 199(prime) ? this is what i tried: made 5x as 204 which would be divisible by 3...then by some algebra and completing the square, i ended up with (x+34)^2=28 mod199 i checked if 28 was QRmod 199..it was, then i got y^2=28 mod199. where y=x+34 can't seem to continue to find a value for y since exponent 2 is not rel. prime with 198(phi199)..please advise, many thanks!

Q; How to solve x^3 = 8 mod 13?

Q: Is there going to be a particular emphasis on the material covered since the midterm or is it going to be evenly distributed throughout the whole course?

Q: Is it possible to update the section on "What we actually covered?" just to be sure we don't leave out anything that we should study for, or study what we didn't cover? Also, in regards to Lecture 19 (not on exam)..what *date* was it taught? Just to confirm.

Q: prove y^2 = x^3 + 7 has no integer solutions

A: suppose ( x , y) is a integer solution such that x is even then let x = 2k then x^3 + 7 = 4(2k^3) + 7 hence y^2 is odd.

let y = 2j + 1 then y^2 = 4(j^2 +j ) +1 = 4(2k^3) + 7 and so dividing by 4 on both sides gives a remainder of 7 on one side and 1 on the other sidecontradiction and so x is odd.

now y^2 + 1 = x^3 +8 = ( x +2 )( x^2 -2x + 4)

since x is odd x^2 - 2x + 4 = 3 mod 4. Now suppose q is prime such that q = 3 mod 4 and q does not divide x^2 - 2x + 4then x^2 -2x + 4 is not equal to m( 3 + 4r ) for r,m integers contradiction since x^2 - 2x + 4 = 3 mod 4. There is a prime q such that q dividesx^2 - 2x + 4.

now consider y^2 + 1 = x^3 + 8 mod q

here q divides x^3 + 8 since q divides x^2 -2x + 4 and so y^2 + 1 = 0 mod q and so -1 is a QR mod q then since q is odd (-1)^(q-1)/2 = 1 mod qby Eulers criterion but (q-1)/2 = 1 + 2p hence (-1)^(q-1)/2 = -1 contradiction

Hence y^2 = x^3 + 7 has no integer solutions (Anthony)

Q:
Show that the equation x2 ≡ a mod 21 has either 1, 2 or 4 solutions modulo 21.

Q: are there any tricks of factoring Gaussian integers like 1+3i and 3+4i? other than by trial and error?

Q: For the proof of the question "If A Gaussian integer Z is a Gaussian prime, then N(Z) is a prime or a square o a prime of the form p=4k+3", we have the following sentence from the answer below: " If z is not an integer then z divides a product of primes in the integers." Can someone explain why we have this causation?

A: Here z divides a product of primes in the integers because (z) ( conjugate of z) = N( z ) and so by the unique factorization in the guassian integers z must divide a prime in the Integers ( Anthony)

Q: Is it possible to update the section on "What we actually covered?" just to be sure we don't leave out anything that we should study for, or study what we didn't cover? Also, in regards to Lecture 19 (not on exam)..what *date* was it taught? Just to confirm.

Q: I know you said that Pell's Equation won't be on the exam; does this mean that nothing from chapters 30-32 from the textbook is going to be on the exam? Also, just to confirm, since the midterm we have covered chapters 23-27, 33, and 34 - is this correct?

Q: How can we find that
x^25 = 1 mod 11, x /= 1 mod 11 and x^25 = 1 mod 43, x /= 1 mod 43 each of these congruences has 4 soultions

Q: What is Unique Factorization in Gaussian Integers?

A: This analogue of Fundamental Theorem of Arithmetic, but for Gaussian integers.
A Gaussian integer p is called prime if whenever p | ab then p|a or p|b.
Now unique factorization for Gaussian integers says that given any Gaussian integer N can be factored into primes. For example in Gaussian integers 2=(1-i)(1+i)

Q: prove the only integral solution to y^2 = x^3 + x is x = 0 and y = 0

A: suppose x^3 + x = y^2 now note x^3 + x = x( x^2 + 1) then note that x and x^2 + 1 are relatively prime and so x^2 + 1 and x are squares since the product is a square.

let k^2 = x^2 +1 then k^2 - x^2 = (k - x)(k + x) = 1 hence by the fundamental theorem of arithmetic in the integers k - x = 1 and k + x = 1 or k - x = - 1 and k + x = -1 and so k = 1 or -1 hence k^2 = 1 and so x = 0 and y = 0

Q: could someone help out with this: x^3 + 4x + 8=0 mod 15? thanks!

A: there are no solutions breaking up 15 = 5(3) check mod 3 x^3 + 4x + 8 = 0 mod 3 here the equation has no solutions in mod 3 and so has no solutions in mod 15.

(Why Not?) let x=2, the 2^3 + 4*2 + 8 = 8 + 8 + 8 = 24 = 0 (mod 3), so by CRT, it does not matter what mod 5 is, you can get a solution 0 mod15.

Q: What is Sum of two Square Theorem?

A: the sum of 2 squares theorem for prime numbers states if p is a prime then p can be written as the sum of 2 squares ie ( p = a^2 + b^2 ) for a , b integers iff p = 1 mod 4.

Q: What is Unique Factorization in Gaussian Integers?

Q:

5cdot 5 = (3+4i)(3-4i)

Why doesn't this equality contradict uniqueness of factorization to prime factors in Gaussian integers?

A: (assuming we are looking for integer solutions) This factors as (x+3y)(x-3y) = 1, and since we are looking for integer x and y, the factors x+3y and x-3y must also be integers. Then by factoring 1, we must have x+3y = 1 and x-3y = 1, or x+3y = -1 and x-3y = -1. In both cases, we find y = 0, and either x = 1 or x = -1. So the two integer solutions are (1,0) and (-1,0).

Q:
Find all the solutions of the equation

x^2-5y^2=1

A: This is a standard Pell's equation. See theorem 32.1 in the textbook. In this case D=5. The procedure for solving such equations is as follows: first find the solution (x_1, y_1) with smallest x_1 by continued fractions (theorem 40.4 in the textbook). Then all the solutions are obtained by taking powers of (x_1, y_1).
sqrt(5)=[2,overbar(4)], (Proposition 40.1 for example). Then p/q=[2,4]=9/4. m=1 is even (for this question), so the desired smallest solution is (9,4). Q
Find infinitely many solutions of the equation

x^2-5y^2=11

(there is no need to find all the solutions)

A: Take a look at exercise 32.1(d) in the textbook. It tells us that one can obtain the solutions to x^2-Dy^2=M (*) by first finding one particular solution to (*) and then combining it with solutions of x^2-Dy^2=1 in a certain way. One particular solution to x^2-5y^2=11 is (4,1) for example.

Q
Factor the Gaussian integer 5+15i into a product of non-unit Gaussian integers which can't be further factored as products of
non-unit Gaussian integers.
A:
5 + 15i = (1 - i)*(1 - 2i)^2 (1 + 2i)

Q:
a) Suppose that N(z)=p^2 for a Gaussian integer z and a prime number p. Show that if p=4k+3, then z is a Gaussian prime. Show that if p=4k+1, then z is not a Gaussian prime.

A:
a)

suppose N(z) = p^2 and let p = 3 mod 4 such that z is not guassian prime then z has nontrivial factorization say z= (a+ib)(c + id) WLOG
then N(z) = (a^2 + b^2)(c^2 + d^2) = p^2

hence a^2 + b^2 = p and c^2 + d^2 = p and so p is a sum of 2 squares but p = 3 mod 4 and from the sum of two squares theorem p cannot be written as the sum of two squares

so z has trivial factorization hence z is guassian prime.

suppose p = 4k + 1 and let z be a guassian prime then conjugate of z is guassian prime and the product of z * (conjugate of z ) is the product of 2 guassian primes.
but N(z) = z * (zbar) = p^2 and since p = 1 mod 4 then p can be written as the sum of 2 squares and hence p is the product of 2 guassian primes and so p^2 is the product of 4
guassian primes contradiction.

NQ: (not a question, but) Proof that -1 is a norm in

that is, there is a solution to x^2+y^2 = -1 mod p.

There must exist some quadratic residue a^2 such that a^2+1 is a quadratic nonresidue modulo p (because if every QR + 1 is a QR, then since 1 is a QR, we must have 1,...,p-1 all QRs, contradicting the fact that there are only (p-1)/2 QRs). But since p = 3 mod 4, -1 is a quadratic nonresidue, so therefore -(a^2+1) is QNR x QNR = a quadratic residue (call it c^2). Thus

and so

as desired.

NA: Cool! (Yura)

Q: Use uniqueness of factorization in Gaussian integers to show that there are no integer solutions of x^3 = y^2 + 1 with odd y.

A: What I meant was "with y even".

With y odd, the right side of the equation is 2 mod 4 and the left side of the equation is 0 mod 4.

So assume y is even.

Factor the right side of the equation as (y-i)(y+i). Now

Let's check whether y+i is divisible by 1+i:

Since y is even, this shows that y+i is not divisible by 1+i. Thus y-i, y+i are coprime.

Hence

for some units u,v. (Indeed, if x^3=mn with m,n relatively prime, then every prime factor of m appears with an exponent divisible by 3. Similarly for n).

Now let s=a+ib so that

Then

In particular comparing the imaginary parts we find that

i.e.

In particular either a or b is equal to plus/minus 1, while the other one is equal to 0. Thus s=a+ib is a unit, and hence y+i=u s^3 is a unit.

This is only possible for y=0, so we find the only solution x=1,y=0.

Q: how many solutions to the equation x^2 + y^2 ≡ 1 mod p

A: If -1 is a quadratic residue modulo p, then we can solve the question as follows:

Let a be such that a^2=-1. Then

Make an invertible change of variables:

(the inverse transformation is given by

)
Then the equation becomes zw≡1 mod p and hence has p-1 solutions (for every non-zero z there is a unique w with zw=1 mod p).

If -1 is not a quadratic residue, the solution above fails.

In this case we can obtain a different solution using a trick with parametrization of the circle we used when discussing pythagorean triples:

If (x_0,y_0) is a solution of x^2+y^2=1 mod p different than (1,0), then the "line" through (1,0),(x_0,y_0) intersects x^2+y^2=1 mod p in two points. Indeed, the system of equations

has at most two solutions because it can be reduced to a quadratic equation modulo a prime number, and it definitely has two solutions ((1.0),(x_0,y_0)).

Conversely, if m is any residue modulo p such that

then the system

has two solutions: (1,0) and

Thus any residue m whose square is not -1 produces a solution and every solution besides (1,0) is obtained this way. Thus if -1 is not a quadratic residue mod p, there are p+1 solutions (p solutions corresponding to different values of m and the solution (1,0)).

So the completeanswer is as follows: if p=2, there are 2 solutions. If p=4k+1, there are p-1 solutions. If p=4k+3, there are p+1 solutions.

Q:
how many guassian primes are there of norm less than 11

A:
there are no guassian primes of norm 0,1,3,4,6,7,8 or 10

the guassian primes of norm 2 are the following
1 + i , 1 - i , -1 - i , -1 + i

the guassian primes of norm 5 are the following
1 + 2i , 1 - 2i , -1 -2i , -1 + 2i , 2 + i , 2 -i , -2 - i , -2 + i

the guassian primes of norm 9 are 3, -3, 3i, -3i

hence there are 16 guassian primes of norm less than 11.

Q:
suppose p is prime integer such that p = mn where m and n are guassian integers and are not units prove conjugate of m is equal to n.

A:
suppose p is prime integer such that p = mn where m and n are not units and m = a+ ib then N(p) = N(m)* N(n) = p^2
hence N(m) divides p^2. Now since m is not a unit N(m) is not equal to 1 and so N(m) = p and so a^2 + b^2 = p
and so m* (conjugate m) = p.
but p = mn and so (conjugate of m) = n

Q:
a Gaussian integer is a Gaussian prime if and only if N(z) is a prime or a square of a prime of the form p=4k+3.

A:
suppose N(z) is prime and z is not a guassian prime then z has a nontrivial factorization hence there is a guassian integer m which divides z
hence N(m) divides N(z) contradiction since N(z) is prime.

suppose z is a guassian prime now if z is an integer z cannot be equal to 2 or congruent to 1 mod 4 since it would then be of the form a^2 + b^2 and would be divisible
by a + ib.

If z is not an integer then z divides a product of primes in the integers. Then since z*(conjugate z ) = N(z) by the unique factorization in guassian integers z divides a
prime integer say p. Hence N(z) divides N(p) = p^2 and so N(z) = p hence N(z) is prime.
(this is what i think Anthony)

For the other part
suppose N(z) = p^2 where p = 3 mod 4 and suppose z is not a guassian prime then z has a nontrivial factorization say z = (a+ ib)( c + di) where neither of the
factors are units. N(z) = (a^2 + b^2)(c^2 + d^2) = p^2 and so a^2 + b^2 = p and c^2 + d^2 = p which implies p can be written as the sum of 2 squares contradiction
by the sum of two squares theorem.

Q:
If z is a guassian prime then N(z) is a square of a prime p where p is congruent to 3 mod 4

A: This is wrong: 2+i is a Gaussian prime of norm 5.

Q:
Are there other solutions to q and r for which a=b(q) + r where a=48 + 27i and b = 1+2i and for which N(r) < N(b). Say, is r = 2 a valid solution?

A: Yes, the solution is not unique. Even in usual integers 5=2*2+1=2*3-1, so you have two choices for the remainder.

Q:
How many Gaussian integers are there of norm 120?

A: Since 120=2^3 3^1 5^1, and the prime 3 (which is congruent to 3 modulo 4) appears to an odd degree, there are no such Gaussian integers.

Q:
Factor the number 7! as a product of Gaussian primes A:

First factor it as a product of usual primes:

Now factor these primes as products of Gaussian primes:

Q:
let N(z) = p^2 where p is prime and z is a guassian integer if p = 3 mod 4 then z is a guassian prime

A:
suppose N(z) = p^2 and let p = 3 mod 4 such that z is not guassian prime then z has nontrivial factorization say z= (a+ib)(c + id)
then N(z) = (a^2 + b^2)(c^2 + d^2) = p^2

hence a^2 + b^2 = p and c^2 + d^2 = p and so p is a sum of 2 squares but p = 3 mod 4 and from the sum of two squares theorem p cannot be written as the sum of two squares

so z has trivial factorization hence z is guassian prime.
(this is what i think Anthony)

Another solution: If

and p is congruent to 3 mod 4, then the factorization of

to Gaussian primes is p^2. Hence z=u p for a unit u. Hence z is a Gaussian prime.

Q:
if p =1 mod 4 and N(z) = p^2 then z is not a Guassian prime

A: If p=1 mod 4, then p is a product of 2 Gaussian primes. Hence p^2 is a product of 4 Gaussian primes.

If z is Gaussian prime, then the conjugate of z is Gaussian prime and hence

is a product of 2 Gaussian primes.

Thus if p =1 mod 4 and N(z) = p^2 then z is not a Guassian prime

Q:
find Guassian integers q and r for which a=b(q) + r where a=48 + 27i and b = 1+2i and for which N(r) < N(b)

N(r) = 2 < 5
hence
the guassian integers q and r are the following
q = 21 - 14i
r = -1 - i

Q:
When is -7 a square mod P?

A:
For p which is not 2 and not 7

Thus it is 1 if and only if p is congruent to 1, 2 or 4 modulo 7.

Q:
Compute

A:
(-32/101) = (-1/101) * (2/101)^5
now (2/101) = -1 since 101 is congruent to 3 mod 8
and (-1/101) = 1 hence (-32/101) = -1

Q:For what primes p the number 5 is a quadratic residue?

Is p=2 a solution as well?

A:
Yes, 5=1^1 mod 2.

Q:
How many quadratic residues are there modulo 31? why is the answer (31-1)/2?

A:
There are 31 possible residues modulo 31: numbers from 0 to 30 represent all of them. Excluding 0 half the values are quadratic residues and half are quadratic non residues hence
the number of quadratic residues is (31-1)/2

Q: If

p=2^k+1

is prime, show that 3 is not a quadratic residue.

Combine this with the result of question 2 from March 1 to conclude that every number not divisible by p is congruent to a power of 3 modulo p.

A: To show that 3 is not a QR, that means (3/p)=-1
based on the formula, (p-1)/2 is even, (3-1)/2=1 and "(p/3)=1 iff p=1". so (p/3)= -1 for sure
then we show that 3 is not a QR.
From March 1st, we know that "a is a quadratic non-residue modulo p if and only if a is a primitive root modulo p" Then we can say 3 is a primitive root mod p and by primitive element thm, every number which is not divisible by p is of the from 3^i for an unique "i" from 0 to p-1. (This is what I think, Kevin Chen)

Q: Why are odd powers of primitive roots exactly the QNR?

A: Let a be a primitive root modulo p. If the number x is a QR, then x=n^2 mod p. If n=a^i mod p, then x=a^(2i) mod p. Thus every QR is an even power of a. Conversely, even powers of a are clearly QR. Thus the remaining (odd) powers of a are the QNR.

Q：

A:

Now (2/101)=-1 because 101=-3 mod 8

Hence
(14/101)=1

Q: Find infinitely many solutions of the equation
x^2 - 5 y^2 = 11 (there is no need to find all the solutions)

How to solve such questions with RHS not equal to 1?

A: One solution is x=4,y=1.

Let now

(see solution of the question below for explanation of what is special about 9+4sqrt(5) )

Then x_k^2-5 y_k^2 = 11.

I am not really sure how to find all possible solutions of this equation.

Q: find the integer solutions to x^2-5y^2 = 1

A:
the integer solutions
the smallest positive integer solution where x and y is greater than zero is x=9 y=4
hence the other positive integer solutions are (x_k,y_k) such that

for integer non-negative k.

Q: Which lectures/questions will quiz 3 cover?

A: Now posted on the main page.

Q: Let p = 2^n + 1 be a prime (n > 0). Show that a is a quadratic non-residue modulo p if and only if a is a primitive root modulo p. The answer below says: "Let c be any primitive root modulo p. Then the other primitive roots are c^i with i relatively prime to p-1. In our case this means c is relatively prime to 2^n, which is the same as saying that c is odd. But odd powers of a primitive root are exactly the quadratic non-residues."
Is this showing both directions of the if and only if?

A:
Yes: the odd powers of a given primitive root c coincide with both sets: the set of quadratic non-residues and the set of primitive roots mod p. Hence these two sets are the same.

Q: Show that any prime number p which is congruent to 1 modulo 6 is a divisor of some number of the form

n^2+3

A:
let p be any prime
suppose p=1 mod 6. Notice that p is an odd prime. Now we want to show -3 is
a square mod p.
(-3/p) = (-1/p)(3/p)
= (-1/p)(-1)^(p-1)/2*(3-1)/2 (p/3)
= (p/3) since p is odd.
now since p=1 mod 6 we also have p=1 mod 3, hence (p/3)=1

hence (-3/p)=1, i.e. -3 is a square mod p. Thus n^2 = -3 mod p for some integer n hence p divides a number of the form n^2 +3.

Q: how many solutions are there to x^2- 9y^2 =1

A:
Integer solutions:
(x-3y)(x+3)=1
Hence x-3y = 1, x+3y=1 or x-3y= - 1, x+3y= -1. Hence x=1 or -1, y=0. There are two integer solutions.

(in rationals there are infinitely many solutions).

Q: If

p=2^k+1

is prime, show that 3 is not a quadratic residue. Combine this (question 2 March 6) with the result of question 2 from March 1 to conclude that every number not divisible by p is congruent to a power of 3 modulo p.

See below
By the question from March 1 this means that 3 is a primitive root modulo p. Thus every non-zero residue modulo p is a power of 3.

Q: For what primes p the number 5 is a quadratic residue?

A:
For p different from 5,

The quadratic residues modulo 5 are 1 and -1. Hence the answer is

Q: What are all the quadratic residues modulo 19.

A:

Hence quadratic residues are 1,4,5,6,7,9,-8,-3,-2.

Q: How many quadratic residues are there modulo 31?

A: (31-1)/2=15

Q: Show that the congruence
has a solution modulo any prime.

A:
let p be any prime
Here if x^2=-1 mod p or x^2=-2 mod p has a solution then -1 or -2 is a quadratic residue mod p.
if neither -2 or -1 is a quadratic residue then they are quadratic non residues. But (-2)(-1) = 2 is a product
of quadratic non residues and hence is a quadratic residue hence x^2= 2 mod p has a solution and so
(x^2+1)(x^2+2)(x^2-2) =0 mod p has a solution.

Q: Let a be a quadratic residue mod p and let p be an odd prime
prove a is not a primitive root mod p

A:
Suppose a is a quadratic residue mod p.
Since p is an odd prime and a is a quadratic residue, a^(p-1)/2 is congruent to 1 mod p by Euler's criterion.

This means that the order a is at most (p-1)/2, so a is not a primitive root.

Q: Let a be a quadratic residue mod p and let p be an odd prime the integer p-a is a quadratic residue mod p if p=1 mod 4
and is a quadratic non residue if p=3 mod4

A:
suppose p is an odd prime and a is a quadratic residue mod p.

now (-1)^(p-1)/2 is equal to 1 when (p-1)/2 is even hence p-1 = 4k for some integer k and so p=1 mod4

(-1)^(p-1)/2 is equal to -1 mod p when (p-1)/2 is odd hence p-1= 4j +2 hence p=3 mod 4

Q: If p = 2^k + 1 is prime, show that 3 is not a quadratic residue.
Combine this with the result of question 2 from March 1 to conclude that every number not divisible by p is congruent to a power of 3 modulo p.

A:

If k>1 and k is even, then this number is equal to

so 3 is a quadratic non-residue modulo p.

If k=1, then p=3 and the question doesn't make sense.

If k is odd, then 2^k+1 = (-1)^k + 1 = 0 mod 3 and hence p is not prime.

Q: Let p = 2^n + 1 be a prime (n > 0). Show that a is a quadratic non-residue modulo p if and only if a is a primitive root modulo p.

A: Let c be any primitive root modulo p. Then the other primitive roots are c^i with i relatively prime to p-1. In our case this means c is relatively prime to 2^n, which is the same as saying that c is odd. But odd powers of a primitive root are exactly the quadratic non-residues.

Q: Show that 4 is not a primitive root modulo any prime p.

my attempt:
Artin's conjecture: 2 is a primitive root modulo for infinitely many primes
if p odd:
then all primitive elements of p is in the form of 2^i, gcd(i,p-1)=1
2^2=4, gcd(2,p-1)=2 for all, thus 4 cannot be a primitive root modulo of any prime
if p=2,
4=0mod2; not a primitive root

is this correct?

A: no!
1) Artin's conjecture is still not proved.
2) It doesn't apply to all primes, only to infinitely many primes.

A solution has been posted below.

Q:
how many primitive roots mod 19 exist? express them in powers of 2, 2 is one primitive root.

i tried phi(18) = 6, so there are six roots. 2 is given as one of them. will 5 7 11 13 17 be other roots since they are relatively prime to 18?

A: 2^5, 2^7, 2^11, 2^13, 2^17 are the other primitive roots

Q:Solve the congruence x^2+x-1 = 0 mod 1
A: Complete the square:

Square roots of 4 modulo 11 are + or - 2. Thus x=-6 -2 = -8 = 3 or x=-6+2=-4 mod 11
1

Q: In the 2009 past midterm, question 1(b): "find all solutions to x^3 + 4x + 8 = 0 (mod 15)." We should start by looking at the same congruence mod 3 and mod 5, but how do you handle polynomials like this (especially since we can't factor or use our quadratic equation tricks)?

A: 3 and 5 are very small numbers: just try all the possibilities. Small tricks: x^3=x for all x by FLT, so x^3+4x+8 = x+4x+8=2x+2 mod 3, so x=-1 mod 3.
x^3+4x+8=x^3-x-2=0 mod 5. x=-2,-1,0,1 ro 2 don't work, so there seem to be no solutions to this congruence.

Q: In class we said that CRT produces a unique solution, although at the same time we are using it as a tool to show that there are multiple possible solutions (eg, question1 quiz 2 and the question answered below 'How many solutions does the congruence 1+x+...+x^23 = 0 (mod111) have?'). Can you please clarify how we are using CRT in these cases.

A: CRT guarantees that there exists only one solution modulo mn to a congruence of the form x=a mod m, x=b mod n if m and n are distinct.

If f is a polynomial, m,n are relatively prime and we try to solve f(x)=0 mod mn, then we can solve f(x)=0 mod m and f(x)=0 mod n. By CRT for each solution of f(x)=0 mod m and for each solution of f(x)=0 mod n we get a solution of f(x)=0 mod mn. Thus if the first congruence has r solutions and the second one has t solutions, then the congruence f(x)=0 mod mn has rt solutions.

Q : Could you provide the full procedure of finding the solutions of x^3 = 8 mod 13 ?

Q：How many elements of order 6 are there modulo 13? List them all. my attempt: you look at all the elements co-prime to 13..from 1 to a12 and check which one raised to 6 gives 1mod13. my answer:1,3,4,9,11 and 12..please verify

A: 4 and 10 are the only elements of order 6 mod 13. This question is answered below.

Q: How many elements of order 5 are there modulo 13? using the same method, i only got one element: 1..

A: First of all, 1 doesn't have order 5, it has order 1 (order is the LEAST power you need to raise it to to get 1.) So in this case, there are no elements of order 5 modulo 13. We proved in class that elements of order k exist only if k divides phi(n). In this case n is 13, phi(13) is 12, so you will only get elements of order 1, 2, 3, 4, 6, or 12. None of order 5.

Q:How many irrational solutions x does the equation x^3 - 5x + 2 = 0 have? Find them explicitly.

A:First try to find rational solutions, which is 2. Use the thm we learned on Jan. 12th," If x=m/n, (m, n coprime) is a root of a polynomial a0x^k+a1x^(k-1)+...+ak=0, then m|ak, n|a0."
Then we kan get (x-2)(x^2+2x-1)=0 and solve x^2+2x-1=0. We get two irrational answers. (That is what I think, I am Kevin Chen :P) Thank you once again Kevin!

Q: Decide whether the equation x^2 - y^2 = 2 has zero, finitely many or infinitely many rational solutions x,y. Justify your answer. A: One way to solve this question would be to factor the left-hand side, to get (x+y)(x-y)=2. So write 2 as a product of two rationals a and b, with x+y=a and x-y=b.
Now given any system of equations
x + y = a
x - y = b
we can add or subtract the equations to get solutions
x = (a + b)/2
y = (a - b)/2
so for every possible way to write 2=ab, with rational a, b, we get rational x and y. There are infinitely many pairs a, b (let a be any nonzero rational number, and b = 2/a), so there are infinitely many solutions x, y.
(for example, 3*(2/3) = 2, so let a=3 and b=2/3. Then x = 11/6 and y = 7/6, and (11/6)^2 - (7/6)^2 = 2.

Q: Quiz2.2.2
Solve the congruence
x = 3 mod 35
x = 2 mod 15
A: we can get x=35a+3 and x=15b+2, then 35a+3=15b+2 i.e 15b-35a=1. Since gcd(35, 15)=5, not 1, so there is no sol'n for "a" and "b". Hence, no such x.
(That is what I think, I am Kevin Chen :P) Thank you very much, Kevin! (Yuri)

Q: Show that if

2^n-1

is prime, then

n|2^n-2

Hint: order of an element modulo a prime p divides p-1 A: Order of the number 2 modulo 2^n-1 is obviously n. Thus n divides (2^n-1)-1 if 2^n-1 is prime. Longer answer: Math @ Stack Exchange

Q: Give a characterization of primes p for which the congruence

x^4 + 1 equiv 0 mod p

has at least one solution.

A: This was answered below.

Q: How many elements of order 6 are there modulo 13? List them all. I got the answer to be 3 elements: 4,10,12 but by checking all numbers. Is there any other way which is less tedious?

A: First of all, 12 is not order 6, it's order 2. So there are only two elements: 4 and 10. Once you've found one element, you can find the others pretty easily. So let's say you've checked and found that 4 is order 6. This means 4^6 = 1 mod 13. Then all other elements of order 6 will be some power of 4 - not 4^2 (because (4^2)^3 = 4^6 = 1 mod 13, so it has order 3), not 4^3 (it has order 2), not 4^4 (has order 3), but 4^5 is fine. Basically - any number relatively prime to 6 (1 or 5) will give you an exponent that will give you another remainder mod 13 of order 6. Say, for another example, you want to find elements of order 10 modulo 31. You find 15 works. Then 15^1, 15^3, 15^7, and 15^9 will give you all elements of order 10 mod 31.

Q: How many polynomials

x^k+a_1x^{k-1}+ldots+a_k

of degree k with coefficients 0 and 1 don't have exactly two roots?

Can such a polynomial have more than two roots?

A: The polynomial can't have more than two roots (there are only two residues, 0 and 1, modulo 2).

As for the number of polynomials f with exactly two roots, the condition is f(0)=0 and f(1)=0. This translates to conditions a_k=0, 1+a_1+...+a_k=0, giving a total of 2^{k-2} polynomials.

Q: Professor, for the midterm, should we expect questions similar to the format which we've been exposed to on our quizzes (suggested problems, etc.), or should we prepare ourselves for proofs, and questions of this nature? Thanks for your time! A: There are three questions that start with "show ..." But these are questions of the same format that appeared in suggested problems (e.g. "show that if p>3 is a divisor of n^2+n+1 then p-1 is divisible by 3").

Q: Could you please post the solutions to the quizzes? I know some of the answers are below, but there are a few missing. Thanks!
A: No, sorry. If you are not certain about one of the quesions, please ask here.

Q: For the midterm, it states that material up to primitive element theorem and its applications will be tested. However, does that mean material up to and including the primitive element theorem and its applications, or does that mean only up to?

A: The test includes questions on primitive element theorem, order of an element and applications of primitive element theorem

Q: Give a characterization of primes p for which the congruence x^4 + 1 = 0 mod p has at least one solution.

A: If x^4=-1 mod p then x^8=1 mod p, so order of x is a divisor of 8, i.e. it is 1, 2, 4 or 8. But x or x^2 or x^4 =1 mod p contradicts x^4=-1 mod p, so order of x is 8. Thus 8|p-1.

Conversely, if 8|p-1, then let y be a primitive root mod p and let x=y^{(p-1)/8}. Then z=x^4=y^{(p-1)/2}= -1 mod p (because z^2=1 mod p, but z is not 1).

Thus the characterization is "those primes p for which p-1 is divisible by 8".

Q: Solve the congruence x^3 = 8 mod 13^3

A: x^3=8 mod 13 has 3 solutions: x=2, x=6, x=5 mod 13.

Consider first the case of x=2 mod 13.

Let x= 2 + 13 y. Then

So we want to solve

or equivalently

This means that y=0 mod 13, i.e. y=13z. This translates to

so z=0 mod 13.

Thus we get a solution x=2 mod 13^3.

Consider now the case x=6 mod 13. Let x=6+13 y. Then we want to solve

(the term with 13^3y^3 is not included, because it is zero modulo 13^3)

or equivalently

or

Since 16+3*36y=0 mod 13, this means 3-9y=0 mod 13 or y=-4 mod 13. Let y=-4+13z and get

or equivalently

or

so z=1 mod 13.

Finally x=6+13*(-4+13(1)) mod 13^3, i.e. x=123 mod 13^3

The case x=5 mod 13 can be considered in a similar fashion.

Q: (repost) Show that every prime divisor p>3 of n^2 + n + 1 is congruent to 1 modulo 6

A: Let's compute the order of n modulo p.

If n=1, then n^2+n+1=3 and p=1 or 3, contradicting p>3.

So n is not 1.

If n^2=1 mod p, then p divides n^2-1=(n-1)(n+1). Hence n=1 or -1 mod p, and hence n^2+n+1=3 or 1 mod p, contradicting that n^n+n+1=0 mod p.

Finally n^3=n(n^2)=n(-1-n)=-n-n^2=1 mod p (we are using here that 1+n+n^2=0 mod p). Thus order of n mod p is 3 and hence 3 divides p-1.

Since p is also odd, it means that p=1 mod 6.

Q: Find all solutions of x^42 = 4 (mod 100)

A: x^ 42=4 mod 100 if and only if x^42=4 mod 4 and x^42 = 4 mod 25.

For the first congruence x^42=0 mod 4 the solutions are x=0 or 2 mod 4, i.e. x=0 mod 2.

For the second congruence notice that x must be relatively prime to 25, so x^20=1 mod 25 by Euler's theorem. Thus the equation x^42=4 mod 25 is equivalent to x^2=4 mod 25, i.e. 25|x^2-4=(x-2)(x+2). Since (x-2) and (x+2) can't be simultaneously divisible by 5, this means that 25|x-2 or 25|x+2. Thus x=2 or -2 mod 25.

Finally combine this with x=0 mod 2 to get the answer x=2 or -2 mod 50 (equivalently x=2, -2, 48, 52 mod 100)

Q: For this problem: x^3 = 8 (mod13^3). I started by trying to solve x^3 = 8 (mod 13) and got x = 2,5,6 (mod13).
From here, I used the method shown in class for each of x = 2,5,6 to arrive at 3 solutions for x^3 = 8 (mod13^3).
Namely, x = 2, -125, 123 (mod 13^3).
Is this the only method of doing the question, or are there any less "tedious" ways?

A: This is the right method. Unfortunately I am not aware of a less tedious method.

Q: Show that every prime divisor p>3 of n^2 + n + 1 is congruent to 1 modulo 6

A: Hint: To show that p-1 is divisible by 3, show that the order of n modulo p is 3. Let me know if you need a more complete answer by reposting this question on the top.

Q: How many polynomials

of degree k with coefficients 0 and 1 don't have any roots modulo 2?

A: The condition is that f(0)=1, f(1)=1 mod 2. The first condition is equivalent to a_k=0 mod 2. The second condition is equivalent to a_1+a_2+...+a_k=0 mod 2. Thus we can choose a_1,...,a_{k-2} in an arbitrary manner and a_{k-1} mod 2 is determined, while a_k=0 mod 2. Thus there are 2^{k-2} such polynomials.

Q: How many solutions does the congruence 1+x+...+x^23 = 0 (mod111) have?

A: Since 111=3x37, the congruence 1+x+...+x^23=0 mod 111 is equivalent to the system of two congruences 1+x+...+x^23=0 mod 3 and
1+x+...+x^23=0 mod 37.

The first of these has 2 solutions x=1 or -1 mod 3 (just try 0, 1 and -1).

For the second equation, notice that 1+x+...+x^23=0 mod 37 is equivalent to (1-x)(1+x+...+x^23)=1-x^24=0 mod 37 and x is not congruent to 1 mod 37. The number of solutions of x^24=1 mod 37 is gcd(24,36)=12. Since x=1 is one of the solutions and we want to exclude it, we get 11 solutions of 1+x+...+x^23=0 mod 37.

By CRT we get 2x11=22 solutions for the original congruence modulo 111.

Q:
find all solutions to x^7 is congruent to 15 mod 137

A: 136=8*17, so 7 is invertible modulo 136. Find the inverse s and the answer is 15^s mod 137.

(s=39, 15^39=121 mod 137)

Q:
find all solutions to x^17 is congruent to 0 mod 137

A: 137 is prime, so 137|x^17 if and only if 137|x.

Q:
if 2^n-1 is prime prove n divides 2^n-2

A: For k<n, 2^k<2^n-1.
Since

this shows that order of 2 mod 2^n-1 is exactly n. Thus n divides (2^n-1)-1=2^n-2.

Q:
Show that 4 is not a primitive root modulo any prime p.

A: If p is odd, then since 4=2^2,

and thus the order of 4 is smaller than p-1.

If p=2, then 4=0 mod 2 and hence is clearly not a primitive root.

Q: How many solutions does x^51 = 1 (mod 137) have.
Note: I solved that x^17 = 1 (mod 137) has 17 solutions. Hence
x^51 = 1 (mod 137) must have at least 17 solutions as well. I am trying to use the fact that there is no x with order 51 to prove that every x st
x^51 = 1 (mod 137) must also satisfy x^17 = 1 (mod 137), hence if this holds then that means it will also have 17 solutions.
Is this the correct approach? Please provide some clues, thank you!

A:
You could do it that way indeed: if x^51=1 mod 137, the order of x mush divide both 51 and 136, hence it must be 1 or 17. In any case x^17=1 mod 137. Conversely if x^17=1 mod 137, then x^51=1 mod 137.

An alternative way: if x^51=1 mod 137, then x^17=1^s=1 mod 137 where s is the inverse of 3 mod 137.

has 17 solutions and then for each solution y the congruence

has only one solution

(because 3x91 = 1 mod 136)

Q: In class we covered the problem x^2 + ax+ b = 0 (mod p). Could you re-explain this example with emphasis on
(i) Why you divided the cases into p=2 and p does not equal 2
(ii) The case when p=2, it suffices to solve x^2 = 0, x^2 + x =0, x^2+1 =0, x^2+x+1=0.

A: (i) The trick with completing the square, or, equivalently, the formula

works only if we can divide by 2. If p is equal to 2, we can't do it, so we have to consider p=2 separately.

(ii) If p=2, the coefficients a, b could only be 0 or 1 mod p. Thus there are only 4 equations to solve and each one of them is easily solvable.

Q: Could you please provide a list of which chapters from the textbook we have covered? Thanks！

A: We covered 1,2,3,5,6,8,9,10,11,12,16,17,18,19,20,21,22,part of 23,part of 24

Q: From the question that was solved below

The solution was x = 3. Why do we not include x = 3 * (k * 7 + 1), k>=1 as other solutions to the congruence?

A: The answer is

which is equivalent to saying x=3+21 k for any integer k.

Q： How many solutions does the congruence x^40= 1 (mod100) have?

A: Since x^40=100m+1, it means that gcd(x,100)=1 (because 1 is divisible by gcd(x,100)).
If x is relatively prime to 100, then x^{\phi(100)}=1 (mod 100). \phi (100)= (4-2)(25-5)=40.
So x is the solution of x^40=1(mod 100) if and only if x is relatively prime to 100.
There exactly \phi(100)=40 distinct (modulo 100) numbers that are relatively prime to 100. Answer:The congruence has 40 solutions

Q: N=pq, where p and q are distinct primes. there exist x and y, such that x*2=y*2 mod N, but x is not congruent to y mod N, and x is not congruent to -y mod N. find p and q.

A: It's impossible to determine p and q: one can have x=y mod p and x=-y mod q for any distinct p and q.

Q:How many solutions does the congruence x^40 is congruent to 2 mod100 have A: This congruence doesn't have a solution. If x^40=2 mod 100, then x is even, but then x^40 is divisible by 4 so can't be equal to 2 mod 100.

Q: I was wondering if you could provide the answers for 18.2 please.

18.2 (a) Show that in fact RSA decryption does work for all messages a, regardless of whether or not they have a common factor with m.
(b) More generally, show that RSA decryption works for all messages a as long as m is a product of distinct primes.
(c) Give an example with m=18 and a=3 where RSA decryption does not work (remember, k must be chosen relatively prime to phi(m)=6).

Parts (a) and (b) are similar to 17.4 which asks to show that b^u as found by Algorithm 17.1 is still a solution for "x^k is congruent to b mod m" if gcd(b,m)>1 but m is a product of distinct primes. u is a solution to ku-phi(m)v=1.

A: a,b) Let N=p_1p_2 ... p_n for distinct primes p_i

RSA algorithm starts with message a and outputs a^{ks} mod N where ks = 1 mod phi(N).

The message a could be divisible by p_i or not divisible by p_i. If it is, then a^{ks}=0=a mod p_i. If a is relatively prime to p_i, then a^phi(N)=1 mod p_i, since phi(N) is divisible by p_i - 1. In particular a^{ks}=a mod p_i. Thus regardless of what a is, a^{ks}=a mod p_i for all i and hence a^{ks}=a mod N by CRT.

Q: Feb 07:Solve the congruence x^2+x-1=0 mod 11 A: 11 is a prime number, so we can divide. x^2+x-1=(x+1/2)^2-5/4=0 (mod 11). 1/4=3 (mod 11), so (x+1/2)^2=4 (mod 11), so x+1/2=2 (mod 11) or x+1/2=-2 (mod 11). 1/2=6 (mod 11), so x=3 (mod 11) or x=7 (mod 11)

Q: general question about fermat: does p have to be necessarily prime?
consider: 7^5=1 mod6, 6 is not prime, only that 7 and 6 are co-prime. please advise, thx.

A: Fermat's little theorem guarantees that if p is prime, then a^(p-1)=1 mod p for all a not divisible by p. It doesn't say anything about whether for a composite number n the equality a^(n-1)=1 mod n holds for some particular values of a. In your example 7^5=1^5=1 mod 6, but the reason has nothing to do with FLT (it has to do with the fact that 1 raised to any power is still 1).

it cannot be sufficient to simply state that since 7*1734250 is not congruent to 1 modm, m is not prime?

A: If m is prime, then by FLT

Since this equality doesn't hold, m is not prime.

Q: Find a multiple of 77 that ends with 999

attempted:
77x=999mod1000 (subtracting 999 from that multiple would leave 3 0s)
but came up with x=12987; clearly wrong, please correct!

A: 12987*77=999999

Q: find the non-negative solutions of 7x+19y=1

A: if x>0 or y>0 then 7x+19y>1. If x=0 and y=0, then 7x+19y=0. Thus there are no non-negative solutions of this equation.

Q:
Show that the congruence
x^2 = a (mod21)
can have 0, 1, 2 or 4 solutions depending on a

I tried to show this by using CRT: since 21 is the product of 3 and 7, I worked with two congruences
(1): x^2=a(mod3) and
(2): x^2=a(mod7)
then showed that both congruences can have 0, 1 or 2 solutions (depending on a) (by solving for a= 0, 1, 2 for (1) and a = 0, 1, 2, ..., 6 for (2)), which
implied that (3): x^2=a(mod 3*7=21) has 0, 1, 2, or 4 solutions (depending on a) (since multiplying the number of solutions for (1) and (2) with the same value of a gives the number of solutions for (3)).
Is this correct or are there any less tedious methods?

A: This is correct.

We have recently learned a theorem that equation of degree n has at most n different roots modulo a prime p, which shows immediately that x^2=a mod 3 and x^2=a mod 7 each have 0,1 or 2 solutions, but without using it what you did is indeed the best way.

Q1 Find 2^220 (mod 221) Conclude that 221 is composite.

A: Use successive squaring:

2^220=4^110=16^55=16*256^27=16*35^27=16*35*1225^13=16*35*120^13=16*35*120*14400^6=16*35*120*35^6=16*35*120*120^3=16*35*120*120*35=16 mod 221

If 221 were prime, then 2^220 would have been 1 mod 221 by FLT. Hence 221 is composite.

Q2 Show that a^48=1 (mod 221) for all a relatively prime to 221.

A: 221=13*17

a^48=a^(12*4)=1 mod 13 by FLT
a^48=a^(16*3)=1 mod 17 by FLT
Thus a^48=1 mod 221 by CRT

Q:Solve the congruence
(*)
A: if x is the solution of (*) we have x^7=3(mod 7), x^7=0(mod 3) so 3|x.
y^6=1(mod 7) for all y that are coprime with 7. So (since our x is clearly coprime with 7)
x^7=x^6*x=x=3(mod 7). So x=0(mod 3) x=3 (mod 7) but chinese remainder theorem
the solution mod 21 is unique and 3 is clearly the solution.

Q: According to Feb 2 lecture, X^24 = 1 (mod 35) has phi(35) = 24 solutions. Why is this?

A: By the Euler theorem any x such that (x,m)=1 satisfies

So for m=35 phi(35)=(5-1)(7-1)=24 so any x that is coprime (and there exactly 24 such x mod 35) with 35 is a solution of x^24=1 (mod 35)
if x is not coprime with 35 then it can't be the solution because (1,35)=1.

A: We should solve
x=3+37k, x=1+87m, or, equivalently, 3+37k=1+87m, i.e. 87 m - 37 k = 2.

Rewrite this as 13m - 37 (k - 2m) = 2 and let k'=k-2m. Rewrite 13m - 37 k' = 2 as 13(m-3k') + 2 k' = 2. One solution is m-3k'=2, k' = - 12. Thus m= -34, k=k'+2m = -80.

Thus x=3+37 k = 3 - 37*80= - 2957.

(This is only one possible solution. Other ones are given by -2957 + 87*37 t with integer t).

Q: Show that for

the congruence

holds for every a relatively prime to m.
(Hint: use Fermat's little theorem to compute a^{m-1} mod p for every prime divisor p of m).

A: This was shown in class Tuesday, January 31.

Q: Find the remainder when a is divided by m (a) a=207^321+689! m=7

(b) a=(123)(45)(678)(910)(112) m=6

A: a) 689! is divisible by 7.
207=(-3) mod 7 and (-3)^6= 1 mod 7 by FLT. Thus 207^321 = (-3)^(53*6+3)= (-3)^3 = 1 mod 7.
b) 678 is divisible by 6, so the whole product is also divisible by 3.

Q: For the following two questions:
9.4 a) Assuming that the congruence

holds, show that 1734251 is a composite (i.e. non-prime) number.
c) The congruence

is true. Can you conclude that 52633 is a prime number?

Is it enough to just show by using Fermat's little theorem?

A: In a) FLT shows that 1734251 is composite.
In c) FLT doesn't show anything.

Q: 8.4 (d) Show that a number is divisible by 9 if and only if its sum of digits is divisible by 9.

A: Let the number be

i.e. the digits are a_0,a_1,...,a_n.

Then

This shows that the remainder of division of the number by 9 is the same as the remainder of division of its sum of digits by 9.

Q: based on 2.1 (b) Show that in a primitive Pythagorean triple a,b,c exactly one of a,b,c is divisible by 5.

A: Modulo 5 all the squares are congruent to 0 or plus/minus 1. If a^2+b^2=c^2 mod 5 and (a,b,c) is not (0,0,0) mod 5, the only options are

In each of these cases exactly one of a,b,c is equal to 0 mod 5.

Q :Find all integer solutions of the equation 65432 x + 98765 y = gcd(65432,98765)

A: 98765=65432+33333, so we rewrite this equation as 65432 x' + 33333 y = gcd (65432, 33333) with x'=x+y.

Next 65432 = 2*33333-1234, so we rewrite the equation as -1234 x' + 33333 y' = gcd ( -1234, 33333) where y' = y+2x'.

Next 33333 = (-27)*(-1234) + 15, so we rewrite the equation as -1234 x'' + 15 y' = gcd ( -1234, 15) where x''=x'-27y'

Next -1234 = (-82)(-15)-4, so we rewrite the equation as -4 x'' + 15 y'' = gcd(-4,15) where y''=y'-82x''

Finally 15 = (-4)(-4)-1, so we rewrite the equation as -4x''' - y'' = gcd(-4,-1)=1, with x'''=x''-4y''.

One solution of this equation is x'''=0, y''=-1, i.e. x''=-4, y'=y''+82x''=-329, x'=x''+27y'=-4+27*(-329)=-8887, y=y'-2x'=-329+2*8887=17445, x=x'-y=-8887-17445=-26332.

All other solutions are given by x=-26332 + 98765 k, y=17445 - 65432 k, k - any integer.

Q : Find 10^5^101 (mod 21)

A: 10=1 mod 3, so 10^5^101 is 1 mod 3.

By FLT, 10^6=1 mod 7. Now we want to divide the exponent 5^101 by 6 with remainder. We see immediately that 5^101=(-1)^101= -1=5 mod 6. Thus 10^(5^101)=10^(6q+5)=10^5 mod 7.
Finally 10^5=3^5=5 mod 7.

Combining these two results using CRT we find that 10^5^101=19 mod 21.

Q: Find a number

with

A: 73 is a prime number, so by FLT 9^72 = 1 mod 73. Now 794=11*72+2, so 9^794=9^2=81=8 mod 73

Q. Show that for a prime number p the number (p-1)!+1 is divisible by p
(Hint: consider the number (p-1)! mod p. In this product one can split most of the residues to pairs of a residue and its inverse).

A: In the product

every residue comes with its inverse modulo p. In general these two residues x and x^{-1} are different from each other, except when x=x^{-1}, or, equivalently, x^2=1, i.e x=1 or -1.

Thus (p-1)!= -1 mod p.

Q.
Does
x^10+y^10 = 11z^10
have non-zero solutions mod 6?

could it be shown using mod 6 instead of 4 from the answer below?

A: For a non-zero x, x^2=1,4,3 mod 6, so x^10=1,4,3 mod 6. Same holds for y^10. 11z^10 is 5,2,3 mod 6.
So 1^10+4^10=11*1^10 mod 6 is a non-zero solution mod 6.

So I don't see an obvious way of concluding non-existence of non-zero solution by trying to do it mod 6 instead of mod 4.

Q. Determine the value of 2^2012+3^3013(mod7)

A:
Compute first 2^2012 mod 7.
2^3=1 mod 7, so 2^2010=1^670=1 mod 7 and so 2^2012=4 mod 7.

Now 3^6=1 mod 7. Apply this to compute 3^3013 mod 7 in the same way: 3^3013=3^3012 * 3 =3 mod 7.

Thus 2^2012+3^3012 = 0 mod 7

Q:2.6) b) Find a Pythagorean triple (a,b,c) with c=a+2 and c>1000. c) Find all primitive Pythagorean triples (a,b,c) with c=a+2.

A: a^2+b^2=(a+2)^2 means 4a+4=b^2. This equation has a solution for every even number b: b=2k, a=k^2-1. If k is odd, a is even and the triple (a,b,a+2) is not primitive. However if k is even, then gcd(k^2-1,k)=gcd(-1,k)=1, so gcd(k^2-1,2k)=1 and thus the triple is primitive.
In short all the primitive solutions are of the form (k^2-1,2k,k^2+1) with even k.

Q: Solve

A:

So the solutions are 3 and -3 mod 7.

Q: Show that there are infinitely many primes of the for 6n+5.

A: First notice that every prime number, except 2 and 3 is congruent to either 1 or -1 mod 6.

Consider the number 6n!-1. All its divisors are at least n and among its prime divisor at least one must be congruent to -1 mod 6 (because the product is congruent to -1 mod 6).

Q: Show that the equation

has no non-zero integer solutions.

A:
We can assume gcd(x,y,z)=1
Let's look at the remainder of the both sides modulo 4.

so x^{10}+y^{10} mod 4 can be 0 (if they are both even), 1 or 2
11z^{10} mod 4 can be 0 (if z is even) or 3.
But
x^{10}+y^{10}=11z^{10}, so both sides are 0 mod 4 and x,y,z are all even,
that condradicts with the assumption gcd(x,y,z)=1.

Q: (2.3) Which odd numbers a can appear in a primitive Pythagorean triple (a,b,c)?

A: Any odd a can appear

Q: Which even numbers b can appear in a primitive Pythagorean triple (a,b,c)?

A:
If b is not divisible by 4 it cannot appear in the Pythagorean triple.
Let's look at the remainders of both sides modulo 8.
a, c are odd so their squares can be only 1 mod 8. If b is not divisible by 4
b^2 mod 8 is 4, so a^2+b^2 mod 8=5 that is not equal to one.
If b is divisible by 4 take b=2^{k}d, where d is odd. We know that k>1.
Then take the Pythagorean triple a=2^{2k-2} - d^{2}, b, c=2^{2k-2} + d^{2}.
Since k>1 a is odd.
gcd(a,b,c)=1 (assume the contrary, there exist prime p that divides a,b,c. Since a is odd p is odd. Odd prime p divides b, so it must divide d, so p must divide a+d^{2} that is a power of two. contradiction).
So we constructed a primitive Pythagorean triple with the given b.

Q: (2.1) We showed that in any primitive Pythagorean triple (a,b,c) either a or b is even. Use the same sort of argument to show that either a or b must be a multiple of 3.

A: Consider the identity a^2+b^2=c^2 mod 3. If neither a nor b are divisible by 3, then

and similarly for b^2. Thus a^2+b^2 = 2 mod 3, which is not a square of anything mod 3.

Thus either a or b must be divisible by 3.

Q: Show that the equation x^2 + x = y^2 has no non-zero integer solutions A:

Since x, (x+1) can't have common divisors if some prime p divides x, then p^2 divides x (since p divides y, so p^2 divides x(x+1) and gcd(x+1,x)=1). So

for some integer a. For the same reason

for some integer b. But it means that we got two plus/minus squares of integers with the difference one, so x=0 or x=-1.

Q: Show that if x, y,z have no common factors and satisfy the equation above (x^2 + 2y^2=z^2)
Then one can find integers s,t such that either z-x=2s^2, z+s=t^2 or z-x=s^2, z+x=2t^2.

A: First of all notice that x,z must be odd (if x is even, z is also even and it follows easily that y must be even as well).

Now rewrite the equation as 2y^2=x^2-z^2=(x-z)(x+z).

Notice that gcd(x-z,x+z)=gcd(x-z, 2x)=2gcd(x,z)=2.

Thus the only common factor of (x-z) and (x+z) is 2.

It follows that all the exponents of the primes other than 2 in the factorizations of x-z and x+z are even. The exponent of 2 is even in one of them and odd in the other one.

Thus either x-z=2s^2, x+z=t^2 or x+z=2s^2, x+z=t^2.

The required parametrization follows.

Q: Solve the equation x^2 + 2y^2=z^2 in integers.

A: See question above.

Q: (2.4)
In our list of examples are the two primitive Pythagorean triples

Find at least one more example of two primitive Pythagorean triples with the same value of c. Can you find three primitive Pythagorean triples with the same c? Can you find more than three?

A: I am sorry for assigning this question: it seems a bit tougher than I expected it to be.

One possible approach to it is to use the following identity:

(we will later learn how this identity naturally appears from some basic properties of complex numbers).

This identity allows you to get a representation of some numbers as sum of two squares in two different ways.

To get a representation of a number as a sum squares in four different ways, use this identity twice:

and now use the identity once again.

Q: Show that

for any natural numbers m,n.

A: We showed in class that if

then

Let's now divide n by m with remainder: n= qm+r. By applying the result above q times, we get that

So if we want to compute gcd(10^x-1,gcd^y-1), we can always replace the pair of parameters (x,y)=(n,m) by the pair (x,y)=(m,r) without changing the answer.

We know from what we have discussed about Euclid's algorithm that we can repeat this procedure until we get to the pair (gcd(m,n),0). For this pair the value of gcd(10^x-1,10^y-1) is

Q:Find an integer solution of

with a>1000 and with a, b, c having no common factor.

A: Let x=a/c, y=b/c. Then we want to find a rational solution x,y to the equation x^2+xy+y^2=3. One solution is x=1, y=1.

We showed in class that all rational solutions of such equation are given by intersecting the quadric with lines of the kind y-1 = m(x-1) with rational m. Plugging the value of y from the equation of the line into the equation of the quadric we find

One solution of this equation is x=1, so the second solution is

and

It remains to choose a large enough m so that the numerator and denominator in the fractions will be large enough, e.g. m=50 that gives a=2398, b= - 5099, c= 2551 (check that these are relatively prime!) .

Q: January 10 question1
Prove that

has no nonzero solutions

A: We can assume that gcd(m,n)=1, otherwise write

then

Now m_1 is divisible by three, so

is divisible by 9, so n_1 is divisible by three. We get the contradictionh with the fact that

Q: January 10 question4
Prove that if

and x,y,z have no common factors, then x and z must be odd and y must be even.

A: Assume x is even, then

is also even, so z is even and

is divisible by 4, so y is even and x,y,z have the common factor 2.
So x is odd and so is z (as a sum of odd and even number). Now if x,z are both odd then

is divisible by 4 and so y is even.

Q: January 10 question3
prove

has no solutions with x and y both odd

A: If x is odd, z must be odd as well. Let x=2k+1, y=2n+1, z=2m+1 the equation translates into 4k^2+4k+8n^2+8n+3=4m^2+4m+1. The left side gives remainder of 3 when divided by 4, while the right side gives remainder of 1. Thus no solution with odd x, y could possibly exist.

Q:
Show that

is irrational. (Hint:

A:

Applying the hint we find that

satisfies the equation

or, equivalently, 8x^3-6x-1=0. By a theorem we proved in class the only candidates for rational solutions of this equation are

By checking each one of these we find that the equation has no rational solutions, so x must be irrational.

Q: Find at least one integer solution to the equation 21x - 13 y = 1

A: Write the equation as 8 x + 13 (x-y) =1, let y'=x-y.
Now solve 8x + 13 y' = 1
Write it as 8 (x+y')+5 y' = 1
Let x'=x+y'
Solve 8x'+5y'=1
Write it as 3x'+5(x'+y')=1
Let y''=x'+y'
Solve 3x'+5y''=1
Write it as 3(x'+y'')+2y''=1
Let x''=x'+y''
Solve 3x''+2y''=1, or x''+2(x''+y'')=1.

One solution: x''=1, x''+y''=0, i.e. x''=1, y''=-1.
Now unwind the substitutions: x'=x''-y''=2
y'=y''-x'=-3
x=x'-y'=5
y=x-y'=8.

Thus one solution is x=5, y=8 (check: 21*5-13*8=105-104=1).

All other solutions are of the form x=5+13k, y=8+21k.

Q: Please provide some hints on how to do the second problem for January 10th:
Show that the equation x^2+x=y^2 has no non-zero integer solutions

Hint: If you want to show that something (x^2+x) is not a square of an integer, try to prove that it
can't fit into the "gap" between two consecuitive squares.

A hint to a different solution: rewrite the equation in the form

and use that x, x+1 are relatively prime.

Q: Show that if

is a rational number, then it is an integer.

A: If n=a^2/b^2 for some integers a, b, then nb^2=a^2. Let p be any prime number and let k_a, k_b, k_n denote the multiplicities of this prime in the prime factorizations of a, b, n respectively. The equality nb^2=a^2 and uniqueness of factorization to primes tells us then that k_n + 2 k_b = 2 k_a. Thus k_n is even.

Hence the prime number factorization of n is of the form

and hence square root of n is integer.
Introduction to Number Theory
Introduction to Number Theory

## Good job, Yura! I hope you will have a wonderful time in the future! -Kevin

## Great material, relatively good text, confusing lectures, terrible TA, nightmare midterm, fair exam. Good times. Congrats to all who survived. spot on!

*Is the median for the course really a C-? That is actually the LOWEST mark i have ever seen for a 300 level Math class! Can we curve it to at least a B-?Here's the grade distribution for the course:

As you see we have 35% of A-, A, A+ grades, the maximum allowed for a course. The fact that we have many students who got a mark below 50 (which means 0-25 on the final exam) does lower the statistics, but doesn't change the fact that the exam and the midterm have been a fair measurement of students' ability to solve problems and apply the material of the course. Once again, I can't curve the grades once I have 35% of A-,A,A+ grades.

LOL. We had 2 TAs: male and female, I think one of them was actually good.

Sorry for confusing you in the lectures. Yura.

x^2= 5 mod (2^13 -1) prime modulus...find all solutions to this congruenceA:

here (2^13) - 1 is prime now note 2^13 - 1 is odd and since (2^13) - 1 = 1 mod 5 then (5/p) = 1 hence 5 is a QR mod (2^13) - 1

now note (2^13) - 1 = 3 mod 4 hence by question 6 page 184

x = 5^[( 2^13)/4] is a solution to x^2 = 5 mod (2^13 - 1)

one solution is x = 5^(2^11)

Q:Professor, are you going to hold office hours this Thursday from 10.30 to 12.30?A: NoQ:From our midterm 3a, the solution says " let a be a primitive root mod 43. Then x1,....x7=1, a^6,....,a^36 mod 43", why is this true? Can you explain the steps in detail?A: I'm not the prof, so I may be wrong. I think it's because since a is a primitive root, we must have a^k=x for each x1, x2, ..., x7. But we have x^7 = 1mod43 => a^k7 = 1mod43 (by substituting x=a^k). But since a is a primitive root, we know that only a^42=1mod43 and since 6*7 = 42, we must thus have 6|k. Therefore we have x1 = 1 = a^0, x2 = a^6, x3 = a^6*2= a^12, ..., x7 = a^6*6 = a^36. can't it be argued that 7 is the order, and hence 7k should divide 42, which is p-1?\

x^2= 5 mod (2^13 -1) prime modulus...find all solutions to this congruenceA:

here (2^13) - 1 is prime now note 2^13 - 1 is odd and since (2^13) - 1 = 1 mod 5 then (5/p) = 1 hence 5 is a QR mod (2^13) - 1

now note (2^13) - 1 = 3 mod 4 hence by question 6 page 184

x = 5^[( 2^13)/4] is a solution to x^2 = 5 mod (2^13 - 1)

one solution is x = 5^(2^11)

Q:Professor, are you going to hold office hours this Thursday from 10.30 to 12.30?A: NoQ:From our midterm 3a, the solution says " let a be a primitive root mod 43. Then x1,....x7=1, a^6,....,a^36 mod 43", why is this true? Can you explain the steps in detail?A: I'm not the prof, so I may be wrong. I think it's because since a is a primitive root, we must have a^k=x for each x1, x2, ..., x7. But we have x^7 = 1mod43 => a^k7 = 1mod43 (by substituting x=a^k). But since a is a primitive root, we know that only a^42=1mod43 and since 6*7 = 42, we must thus have 6|k. Therefore we have x1 = 1 = a^0, x2 = a^6, x3 = a^6*2= a^12, ..., x7 = a^6*6 = a^36. can't it be argued that 7 is the order, and hence 7k should divide 42, which is p-1?

Q:if n is an integer s.t n > 1 then n does not divide (2^n) - 1A:suppose p is the smallest prime divisor of n in the factorization of n into distinct primes then gcd (n , p - 1) = 1 hence there are integers k and ssuch that n(s) + k(p - 1) = 1. now suppose p divides (2^n) - 1 then 2^n = 1 mod p and since p does not divide 2 then 2^( p - 1) = 1 mod pbut 2 = 2^( n(s) + k( p - 1)) = (2^ n)(s)) ( 2^( p - 1)(k)) = 1 mod pcontradictionhence p does not divide (2^n) - 1 and since p is the smallest divisor of n, n does not divide (2^n) - 1Q: prove a^(2^n) = 1 mod 2^(n + 2) where a is oddA:suppose a is odd then a = 2k + 1 k integer now 2^n = 2( 2^(n-1)) hence a^(2^n) = (a^2)(2^(n -1)).now 2^(n + 2) = 4(2^n) and a^2 = 4k^2 + 4k + 1 hence a^2 = 1 mod 2^(n + 2)a^2(2^(n - 1)) = 1^(2^(n - 1)) = 1 mod 2^( n + 2)hence a^(2^n) = a^2(2^( n - 1)) =1 mod 2^( n + 2)how do you approach a question like 3x^2 + 5x +1=0 mod 199(prime) ?this is what i tried: made 5x as 204 which would be divisible by 3...then by some algebra and completing the square, i ended up with (x+34)^2=28 mod199i checked if 28 was QRmod 199..it was, then i got y^2=28 mod199. where y=x+34 can't seem to continue to find a value for y since exponent 2 is not rel. prime with 198(phi199)..please advise, many thanks!Q; How to solve x^3 = 8 mod 13?Q: Is there going to be a particular emphasis on the material covered since the midterm or is it going to be evenly distributed throughout the whole course?Q: Is it possible to update the section on "What we actually covered?" just to be sure we don't leave out anything that we shouldstudyfor, orstudywhat we didn't cover? Also, in regards to Lecture 19 (not on exam)..what *date* was it taught? Just toconfirm.Q:prove y^2 = x^3 + 7 has no integer solutionsA:suppose ( x , y) is a integer solution such that x is even then let x = 2k then x^3 + 7 = 4(2k^3) + 7 hence y^2 is odd.let y = 2j + 1 then y^2 = 4(j^2 +j ) +1 = 4(2k^3) + 7 and so dividing by 4 on both sides gives a remainder of 7 on one side and 1 on the other sidecontradiction and so x is odd.now y^2 + 1 = x^3 +8 = ( x +2 )( x^2 -2x + 4)since x is odd x^2 - 2x + 4 = 3 mod 4. Now suppose q is prime such that q = 3 mod 4 and q does not divide x^2 - 2x + 4then x^2 -2x + 4 is not equal to m( 3 + 4r ) for r,m integers contradiction since x^2 - 2x + 4 = 3 mod 4. There is a prime q such that q dividesx^2 - 2x + 4.now consider y^2 + 1 = x^3 + 8 mod qhere q divides x^3 + 8 since q divides x^2 -2x + 4 and so y^2 + 1 = 0 mod q and so -1 is a QR mod q then since q is odd (-1)^(q-1)/2 = 1 mod qby Eulers criterion but (q-1)/2 = 1 + 2p hence (-1)^(q-1)/2 = -1 contradictionHence y^2 = x^3 + 7 has no integer solutions (Anthony)Q:Show that the equation x2 ≡ a mod 21 has either 1, 2 or 4 solutions modulo 21.

Q: are there any tricks of factoring Gaussian integers like 1+3i and 3+4i? other than by trial and error?Q: For the proof of the question "If A Gaussian integer Z is a Gaussian prime, then N(Z) is a prime or a square o a prime of theformp=4k+3", we have the following sentence from theanswerbelow: " If z is not an integer then z divides aproductof primes in the integers." Can someone explain why we have this causation?A:Here z divides aproductof primes in the integers because (z) ( conjugate of z) = N( z ) and soby the unique factorization in the guassian integers z must divide a prime in the Integers( Anthony)Q: Is it possible to update the section on "What we actually covered?" just to be sure we don't leave out anything that we shouldstudyfor, orstudywhat we didn't cover? Also, in regards to Lecture 19 (not on exam)..what *date* was it taught? Just toconfirm.Q: I know you said that Pell's Equation won't be on the exam; does this mean that nothing from chapters 30-32 from the textbook is going to be on the exam? Also, just toconfirm, since the midterm we have covered chapters 23-27, 33, and 34 - is this correct?Q:How can we find thatx^25 = 1 mod 11, x /= 1 mod 11 and x^25 = 1 mod 43, x /= 1 mod 43 each of these congruences has 4 soultions

Q:What is Unique Factorization in Gaussian Integers?A: This analogue of Fundamental Theorem of Arithmetic, but for Gaussian integers.

A Gaussian integer p is called prime if whenever p | ab then p|a or p|b.

Now unique factorization for Gaussian integers says that given any Gaussian integer N can be factored into primes. For example in Gaussian integers 2=(1-i)(1+i)

Q: prove the only integral solution to y^2 = x^3 + x is x = 0 and y = 0A:suppose x^3 + x = y^2 now note x^3 + x = x( x^2 + 1) then note that x and x^2 + 1 are relatively primeand so x^2 + 1 and x are squares since the product is a square.let k^2 = x^2 +1 then k^2 - x^2 = (k - x)(k + x) = 1hence by the fundamental theorem of arithmetic in the integers k - x = 1 and k + x = 1or k - x = - 1 and k + x = -1 and so k = 1 or -1 hence k^2 = 1 and so x = 0 and y = 0Q: could someone help out with this: x^3 + 4x + 8=0 mod 15? thanks!A:there are no solutionsbreaking up 15 = 5(3) check mod 3x^3 + 4x + 8 = 0 mod 3here the equation has no solutions in mod 3 and so has no solutions in mod 15.(Why Not?)let x=2, the 2^3 + 4*2 + 8 = 8 + 8 + 8 = 24 = 0 (mod 3), so by CRT, it does not matter what mod 5 is, you can get a solution 0 mod15.Q:What is Sum of two Square Theorem?A:the sum of 2 squares theorem for prime numbers states if p is a prime then p can be written asthe sum of 2 squares ie ( p = a^2 + b^2 ) for a , b integers iff p = 1 mod 4.Q:What is Unique Factorization in Gaussian Integers?Q:Why doesn't this equality contradict uniqueness of factorization to prime factors in Gaussian integers?

A: 5 * 5 = (3 + 4i)(3 - 4i) = (2 - i)^2 (2 + i)^2

Q:Factor 65 as a product of Gaussian primes

A:

65 = 13(5) = (2+ i)( 2 - i)( 2 - 3i )( 2 + 3i )

Q:Find all the solutions of the equation

A: (assuming we are looking for integer solutions) This factors as (x+3y)(x-3y) = 1, and since we are looking for integer x and y, the factors x+3y and x-3y must also be integers. Then by factoring 1, we must have x+3y = 1 and x-3y = 1, or x+3y = -1 and x-3y = -1. In both cases, we find y = 0, and either x = 1 or x = -1. So the two integer solutions are (1,0) and (-1,0).

Q:Find all the solutions of the equation

A: This is a standard Pell's equation. See theorem 32.1 in the textbook. In this case D=5. The procedure for solving such equations is as follows: first find the solution (x_1, y_1) with smallest x_1 by continued fractions (theorem 40.4 in the textbook). Then all the solutions are obtained by taking powers of (x_1, y_1).

sqrt(5)=[2,overbar(4)], (Proposition 40.1 for example). Then p/q=[2,4]=9/4. m=1 is even (for this question), so the desired smallest solution is (9,4).

QFind infinitely many solutions of the equation

(there is no need to find all the solutions)

A: Take a look at exercise 32.1(d) in the textbook. It tells us that one can obtain the solutions to x^2-Dy^2=M (*) by first finding one particular solution to (*) and then combining it with solutions of x^2-Dy^2=1 in a certain way. One particular solution to x^2-5y^2=11 is (4,1) for example.

QFactor the Gaussian integer 5+15i into a product of non-unit Gaussian integers which can't be further factored as products of

non-unit Gaussian integers.

A:

5 + 15i = (1 - i)*(1 - 2i)^2 (1 + 2i)

Q:a) Suppose that N(z)=p^2 for a Gaussian integer z and a prime number p. Show that if p=4k+3, then z is a Gaussian prime. Show that if p=4k+1, then z is not a Gaussian prime.

A:

a)

suppose N(z) = p^2 and let p = 3 mod 4 such that z is not guassian prime then z has nontrivial factorization say z= (a+ib)(c + id) WLOG

then N(z) = (a^2 + b^2)(c^2 + d^2) = p^2

hence a^2 + b^2 = p and c^2 + d^2 = p and so p is a sum of 2 squares but p = 3 mod 4 and from the sum of two squares theorem p cannot be written as the sum of two squares

so z has trivial factorization hence z is guassian prime.

suppose p = 4k + 1 and let z be a guassian prime then conjugate of z is guassian prime and the product of z * (conjugate of z ) is the product of 2 guassian primes.

but N(z) = z * (zbar) = p^2 and since p = 1 mod 4 then p can be written as the sum of 2 squares and hence p is the product of 2 guassian primes and so p^2 is the product of 4

guassian primes contradiction.

NQ: (not a question, but) Proof that -1 is a norm inthat is, there is a solution to x^2+y^2 = -1 mod p.

There must exist some quadratic residue a^2 such that a^2+1 is a quadratic nonresidue modulo p (because if every QR + 1 is a QR, then since 1 is a QR, we must have 1,...,p-1 all QRs, contradicting the fact that there are only (p-1)/2 QRs). But since p = 3 mod 4, -1 is a quadratic nonresidue, so therefore -(a^2+1) is QNR x QNR = a quadratic residue (call it c^2). Thus

and so

as desired.

NA: Cool! (Yura)Q:Use uniqueness of factorization in Gaussian integers to show that there are no integer solutions of x^3 = y^2 + 1 with odd y.A: What I meant was "with y even".With y odd, the right side of the equation is 2 mod 4 and the left side of the equation is 0 mod 4.

So assume y is even.

Factor the right side of the equation as (y-i)(y+i). Now

Let's check whether y+i is divisible by 1+i:

Since y is even, this shows that y+i is not divisible by 1+i. Thus y-i, y+i are coprime.

Hence

for some units u,v. (Indeed, if x^3=mn with m,n relatively prime, then every prime factor of m appears with an exponent divisible by 3. Similarly for n).

Now let s=a+ib so that

Then

In particular comparing the imaginary parts we find that

i.e.

In particular either a or b is equal to plus/minus 1, while the other one is equal to 0. Thus s=a+ib is a unit, and hence y+i=u s^3 is a unit.

This is only possible for y=0, so we find the only solution x=1,y=0.

Q:how many solutions to the equation x^2 + y^2 ≡ 1 mod pA: If -1 is a quadratic residue modulo p, then we can solve the question as follows:

Let a be such that a^2=-1. Then

Make an invertible change of variables:

(the inverse transformation is given by

)

Then the equation becomes zw≡1 mod p and hence has p-1 solutions (for every non-zero z there is a unique w with zw=1 mod p).

If -1 is not a quadratic residue, the solution above fails.

In this case we can obtain a different solution using a trick with parametrization of the circle we used when discussing pythagorean triples:

If (x_0,y_0) is a solution of x^2+y^2=1 mod p different than (1,0), then the "line" through (1,0),(x_0,y_0) intersects x^2+y^2=1 mod p in two points. Indeed, the system of equations

has at most two solutions because it can be reduced to a quadratic equation modulo a prime number, and it definitely has two solutions ((1.0),(x_0,y_0)).

Conversely, if m is any residue modulo p such that

then the system

has two solutions: (1,0) and

Thus any residue m whose square is not -1 produces a solution and every solution besides (1,0) is obtained this way. Thus if -1 is not a quadratic residue mod p, there are p+1 solutions (p solutions corresponding to different values of m and the solution (1,0)).

So the

completeansweris as follows: if p=2, there are 2 solutions. If p=4k+1, there are p-1 solutions. If p=4k+3, there are p+1 solutions.Q:how many guassian primes are there of norm less than 11

A:there are no guassian primes of norm 0,1,3,4,6,7,8 or 10

the guassian primes of norm 2 are the following

1 + i , 1 - i , -1 - i , -1 + i

the guassian primes of norm 5 are the following

1 + 2i , 1 - 2i , -1 -2i , -1 + 2i , 2 + i , 2 -i , -2 - i , -2 + i

the guassian primes of norm 9 are 3, -3, 3i, -3i

hence there are 16 guassian primes of norm less than 11.

Q:suppose p is prime integer such that p = mn where m and n are guassian integers and are not units prove conjugate of m is equal to n.

A:suppose p is prime integer such that p = mn where m and n are not units and m = a+ ib then N(p) = N(m)* N(n) = p^2

hence N(m) divides p^2. Now since m is not a unit N(m) is not equal to 1 and so N(m) = p and so a^2 + b^2 = p

and so m* (conjugate m) = p.

but p = mn and so (conjugate of m) = n

Q:a Gaussian integer is a Gaussian prime if and only if N(z) is a prime or a square of a prime of the form p=4k+3.

A:

suppose N(z) is prime and z is not a guassian prime then z has a nontrivial factorization hence there is a guassian integer m which divides z

hence N(m) divides N(z) contradiction since N(z) is prime.

suppose z is a guassian prime now if z is an integer z cannot be equal to 2 or congruent to 1 mod 4 since it would then be of the form a^2 + b^2 and would be divisible

by a + ib.

If z is not an integer then z divides a product of primes in the integers. Then since z*(conjugate z ) = N(z) by the unique factorization in guassian integers z divides a

prime integer say p. Hence N(z) divides N(p) = p^2 and so N(z) = p hence N(z) is prime.

(this is what i think Anthony)

For the other part

suppose N(z) = p^2 where p = 3 mod 4 and suppose z is not a guassian prime then z has a nontrivial factorization say z = (a+ ib)( c + di) where neither of the

factors are units. N(z) = (a^2 + b^2)(c^2 + d^2) = p^2 and so a^2 + b^2 = p and c^2 + d^2 = p which implies p can be written as the sum of 2 squares contradiction

by the sum of two squares theorem.

Q:

If z is a guassian prime then N(z) is a square of a prime p where p is congruent to 3 mod 4

A: This is wrong: 2+i is a Gaussian prime of norm 5.

Q:Are there other solutions to q and r for which a=b(q) + r where a=48 + 27i and b = 1+2i and for which N(r) < N(b). Say, is r = 2 a valid solution?

A: Yes, the solution is not unique. Even in usual integers 5=2*2+1=2*3-1, so you have two choices for the remainder.Q:How many Gaussian integers are there of norm

120?A: Since 120=2^3 3^1 5^1, and the prime 3 (which is congruent to 3 modulo 4) appears to an odd degree, there are no such Gaussian integers.Q:Factor the number 7! as a product of Gaussian primes

A:First factor it as a product of usual primes:

Now factor these primes as products of Gaussian primes:

Q:let N(z) = p^2 where p is prime and z is a guassian integer if p = 3 mod 4 then z is a guassian prime

A:suppose N(z) = p^2 and let p = 3 mod 4 such that z is not guassian prime then z has nontrivial factorization say z= (a+ib)(c + id)

then N(z) = (a^2 + b^2)(c^2 + d^2) = p^2

hence a^2 + b^2 = p and c^2 + d^2 = p and so p is a sum of 2 squares but p = 3 mod 4 and from the sum of two squares theorem p cannot be written as the sum of two squares

so z has trivial factorization hence z is guassian prime.

(this is what i think Anthony)

Another solution: If

and p is congruent to 3 mod 4, then the factorization of

to Gaussian primes is p^2. Hence z=u p for a unit u. Hence z is a Gaussian prime.

Q:if p =1 mod 4 and N(z) = p^2 then z is not a Guassian prime

A: If p=1 mod 4, then p is a product of 2 Gaussian primes. Hence p^2 is a product of 4 Gaussian primes.If z is Gaussian prime, then the conjugate of z is Gaussian prime and hence

is a product of 2 Gaussian primes.

Thus if p =1 mod 4 and N(z) = p^2 then z is not a Guassian prime

Q:find Guassian integers q and r for which a=b(q) + r where a=48 + 27i and b = 1+2i and for which N(r) < N(b)

A:note that N(1+2i) = 5

consider r= -1 - i

48 + 27i - (-1-i) = 49 + 28i

[49 + 28i(1-2i)] / 5

= 21 - 14i

N(r) = 2 < 5

hence

the guassian integers q and r are the following

q = 21 - 14i

r = -1 - i

Q:When is -7 a square mod P?

A:For p which is not 2 and not 7

Thus it is 1 if and only if p is congruent to 1, 2 or 4 modulo 7.

Q:Compute

A:

(-32/101) = (-1/101) * (2/101)^5

now (2/101) = -1 since 101 is congruent to 3 mod 8

and (-1/101) = 1 hence (-32/101) = -1

Q:For what primes p the number 5 is a quadratic residue?Is p=2 a solution as well?

A:Yes, 5=1^1 mod 2.

Q:How many quadratic residues are there modulo 31?

why is theanswer(31-1)/2?A:There are 31 possible residues modulo 31: numbers from 0 to 30 represent all of them. Excluding 0 half the values are quadratic residues and half are quadratic non residues hence

the number of quadratic residues is (31-1)/2

Q:If

is prime, show that 3 is not a quadratic residue.

Combine this with the result of question 2 from March 1 to

conclude that every number not divisible by p is congruent to a power of 3 modulo p.A: To show that 3 is not a QR, that means (3/p)=-1

based on the formula, (p-1)/2 is

even, (3-1)/2=1 and "(p/3)=1 iff p=1". so (p/3)= -1 for surethen we show that 3 is not a QR.

From March 1st, we know that

"a is a quadratic non-residue modulo p if and only if a is a primitive root modulo p"

Then we can say 3 is a primitive root mod p

and by primitive element thm, every number which is not divisible by p is of the from 3^i for an unique "i" from 0 to p-1.

(This is what I think, Kevin Chen)

Q:Why are odd powers of primitive roots exactly the QNR?A: Let a be a primitive root modulo p. If the number x is a QR, then x=n^2 mod p. If n=a^i mod p, then x=a^(2i) mod p. Thus every QR is an even power of a. Conversely, even powers of a are clearly QR. Thus the remaining (odd) powers of a are the QNR.

Q：A:

Now (2/101)=-1 because 101=-3 mod 8

Hence

(14/101)=1

Q:Find infinitely many solutions of the equationx^2 - 5 y^2 = 11 (there is no need to find all the solutions)

How to solve such questions with RHS not equal to 1?

A: One solution is x=4,y=1.

Let now

(see solution of the question below for explanation of what is special about 9+4sqrt(5) )

Then x_k^2-5 y_k^2 = 11.

I am not really sure how to find all possible solutions of this equation.

Q: find the integer solutions to x^2-5y^2 = 1

A:

the integer solutions

the smallest positive integer solution where x and y is greater than zero is x=9 y=4

hence the other positive integer solutions are (x_k,y_k) such that

for integer non-negative k.

Q:Which lectures/questions will quiz 3 cover?A: Now posted on the main page.

Q:Let p = 2^n + 1 be a prime (n > 0). Show that a is a quadratic non-residue modulo pif and only ifa is a primitive root modulo p. The answer below says: "Let c be any primitive root modulo p. Then the other primitive roots are c^i with i relatively prime to p-1. In our case this means c is relatively prime to 2^n, which is the same as saying that c is odd. But odd powers of a primitive root are exactly the quadratic non-residues."Is this showing both directions of the if and only if?

A:

Yes: the odd powers of a given primitive root c coincide with both sets: the set of quadratic non-residues and the set of primitive roots mod p. Hence these two sets are the same.

Q:Show that any prime number p which is congruent to 1 modulo 6 is a divisor of some number of the formA:

let p be any prime

suppose p=1 mod 6. Notice that p is an odd prime. Now we want to show -3 is

a square mod p.

(-3/p) = (-1/p)(3/p)

= (-1/p)(-1)^(p-1)/2*(3-1)/2 (p/3)

= (p/3) since p is odd.

now since p=1 mod 6 we also have p=1 mod 3, hence (p/3)=1

hence (-3/p)=1, i.e. -3 is a square mod p. Thus n^2 = -3 mod p for some integer n hence p divides a number of the form n^2 +3.

Q: how many solutions are there to x^2- 9y^2 =1

A:

Integer solutions:

(x-3y)(x+3)=1

Hence x-3y = 1, x+3y=1 or x-3y= - 1, x+3y= -1. Hence x=1 or -1, y=0. There are two integer solutions.

(in rationals there are infinitely many solutions).

Q: If

Combine this (question 2 March 6) with the result of question 2 from March 1 to conclude that every number not divisible by p is congruent to a power of 3 modulo p.See below

By the question from March 1 this means that 3 is a primitive root modulo p. Thus every non-zero residue modulo p is a power of 3.

Q: For what primes p the number 5 is a quadratic residue?

A:

For p different from 5,

The quadratic residues modulo 5 are 1 and -1. Hence the answer is

Q: What are all the quadratic residues modulo 19.

A:

Hence quadratic residues are 1,4,5,6,7,9,-8,-3,-2.

Q: How many quadratic residues are there modulo 31?

A: (31-1)/2=15

Q: Show that the congruence

has a solution modulo any prime.

A:

let p be any prime

Here if x^2=-1 mod p or x^2=-2 mod p has a solution then -1 or -2 is a quadratic residue mod p.

if neither -2 or -1 is a quadratic residue then they are quadratic non residues. But (-2)(-1) = 2 is a product

of quadratic non residues and hence is a quadratic residue hence x^2= 2 mod p has a solution and so

(x^2+1)(x^2+2)(x^2-2) =0 mod p has a solution.

Q:Let a be a quadratic residue mod p and let p be an odd primeprove a is not a primitive root mod p

A:Suppose a is a quadratic residue mod p.

Since p is an odd prime and a is a quadratic residue, a^(p-1)/2 is congruent to 1 mod p by Euler's criterion.

This means that the

ordera is at most (p-1)/2, so a is not a primitive root.Q:Let a be a quadratic residue mod p and let p be an odd prime the integer p-a is a quadratic residue mod p if p=1 mod 4and is a quadratic non residue if p=3 mod4

A:suppose p is an odd prime and a is a quadratic residue mod p.

now (-1)^(p-1)/2 is equal to 1 when (p-1)/2 is even hence p-1 = 4k for some integer k and so p=1 mod4

(-1)^(p-1)/2 is equal to -1 mod p when (p-1)/2 is odd hence p-1= 4j +2 hence p=3 mod 4

Q:If p = 2^k + 1 is prime, show that 3 is not a quadratic residue.Combine this with the result of question 2 from March 1 to conclude that every number not divisible by p is congruent to a power of 3 modulo p.

A:If k>1 and k is even, then this number is equal to

so 3 is a quadratic non-residue modulo p.

If k=1, then p=3 and the question doesn't make sense.

If k is odd, then 2^k+1 = (-1)^k + 1 = 0 mod 3 and hence p is not prime.

Q:Let p = 2^n + 1 be a prime (n > 0). Show that a is a quadratic non-residue modulo p if and only if a is a primitive root modulo p.A:Let c be any primitive root modulo p. Then the other primitive roots are c^i with i relatively prime to p-1. In our case this means c is relatively prime to 2^n, which is the same as saying that c is odd. But odd powers of a primitive root are exactly the quadratic non-residues.Q:Show that 4 is not a primitive root modulo any prime p.my attempt:

Artin's conjecture: 2 is a primitive root modulo for infinitely many primes

if p odd:

then all primitive elements of p is in the form of 2^i, gcd(i,p-1)=1

2^2=4, gcd(2,p-1)=2 for all, thus 4 cannot be a primitive root modulo of any prime

if p=2,

4=0mod2; not a primitive root

is this correct?

A: no!

1) Artin's conjecture is still not proved.

2) It doesn't apply to all primes, only to infinitely many primes.

A solution has been posted below.

Q:how many primitive roots mod 19 exist? express them in powers of 2, 2 is one primitive root.

i tried phi(18) = 6, so there are six roots. 2 is given as one of them. will 5 7 11 13 17 be other roots since they are relatively prime to 18?

A: 2^5, 2^7, 2^11, 2^13, 2^17 are the other primitive rootsQ:Solve the congruence x^2+x-1 = 0 mod 1A: Complete the square:

Square roots of 4 modulo 11 are + or - 2. Thus x=-6 -2 = -8 = 3 or x=-6+2=-4 mod 11

1

Q:In the 2009 past midterm, question 1(b): "find all solutions to x^3 + 4x + 8 = 0 (mod 15)." We should start by looking at the same congruence mod 3 and mod 5, but how do you handle polynomials like this (especially since we can't factor or use our quadratic equation tricks)?A: 3 and 5 are very small numbers: just try all the possibilities. Small tricks: x^3=x for all x by FLT, so x^3+4x+8 = x+4x+8=2x+2 mod 3, so x=-1 mod 3.

x^3+4x+8=x^3-x-2=0 mod 5. x=-2,-1,0,1 ro 2 don't work, so there seem to be no solutions to this congruence.

Q:In class we said that CRT produces a unique solution, although at the same time we are using it as a tool to show that there are multiple possible solutions (eg, question1 quiz 2 and the question answered below 'How many solutions does the congruence 1+x+...+x^23 = 0 (mod111) have?'). Can you please clarify how we are using CRT in these cases.A: CRT guarantees that there exists only one solution modulo mn to a congruence of the form x=a mod m, x=b mod n if m and n are distinct.

If f is a polynomial, m,n are relatively prime and we try to solve f(x)=0 mod mn, then we can solve f(x)=0 mod m and f(x)=0 mod n. By CRT for each solution of f(x)=0 mod m and for each solution of f(x)=0 mod n we get a solution of f(x)=0 mod mn. Thus if the first congruence has r solutions and the second one has t solutions, then the congruence f(x)=0 mod mn has rt solutions.

Q :Could you provide the full procedure of finding the solutions of x^3 = 8 mod 13 ?Q：How many elements of order 6 are there modulo 13? List them all.my attempt: you look at all the elements co-prime to 13..from 1 to a12 and check which one raised to 6 gives 1mod13.

my answer:1,3,4,9,11 and 12..please verify

A:4 and 10 are the only elements of order 6 mod 13. This question is answered below.Q:How many elements of order 5 are there modulo 13?using the same method, i only got one element: 1..

A:First of all, 1 doesn't have order 5, it has order 1 (order is the LEAST power you need to raise it to to get 1.) So in this case, there are no elements of order 5 modulo 13. We proved in class that elements of order k exist only if k divides phi(n). In this case n is 13, phi(13) is 12, so you will only get elements of order 1, 2, 3, 4, 6, or 12. None of order 5.Q:How many irrational solutions x does the equation x^3 - 5x + 2 = 0 have? Find them explicitly.A:First try to find rational solutions, which is 2. Use the thm we learned on Jan. 12th," If x=m/n, (m, n coprime) is a root of a polynomial a0x^k+a1x^(k-1)+...+ak=0, then m|ak, n|a0."Then we kan get (x-2)(x^2+2x-1)=0 and solve x^2+2x-1=0. We get two irrational answers. (That is what I think, I am Kevin Chen :P) Thank you once again Kevin!

Q: Decide whether the equation x^2 - y^2 = 2 has zero, finitely many or infinitely many rational solutions x,y. Justify your answer.A:One way to solve this question would be to factor the left-hand side, to get (x+y)(x-y)=2. So write 2 as a product of two rationals a and b, with x+y=a and x-y=b.Now given any

systemof equationsx + y = a

x - y = b

we can

addor subtract the equations to get solutionsx = (a + b)/2

y = (a - b)/2

so for every possible way to write 2=ab, with rational a, b, we get rational x and y. There are infinitely many pairs a, b (let a be any nonzero rational number, and b = 2/a), so there are infinitely many solutions x, y.

(for example, 3*(2/3) = 2, so let a=3 and b=2/3. Then x = 11/6 and y = 7/6, and (11/6)^2 - (7/6)^2 = 2.

Q: Quiz2.2.2Solve the congruence

x = 3 mod 35

x = 2 mod 15

A: we can get x=35a+3 and x=15b+2, then 35a+3=15b+2 i.e 15b-35a=1. Since gcd(35, 15)=5, not 1, so there is no sol'n for "a" and "b". Hence, no such x.

(That is what I think, I am Kevin Chen :P) Thank you very much, Kevin! (Yuri)

Q:Show that if

is prime, then

Hint: order of an element modulo a prime p divides p-1

A: Order of the number 2 modulo 2^n-1 is obviously n. Thus n divides (2^n-1)-1 if 2^n-1 is prime.

Longer answer: Math @ Stack Exchange

Q:Give a characterization of primes p for which the congruence

has at least one solution.

A: This was answered below.

Q:How many elements of order 6 are there modulo 13? List them all.

I got the answer to be 3 elements: 4,10,12 but by checking all numbers. Is there any other way which is less tedious?

A:First of all, 12 is not order 6, it's order 2. So there are only two elements: 4 and 10.Once you've found one element, you can find the others pretty easily. So let's say you've checked and found that 4 is order 6. This means 4^6 = 1 mod 13. Then all other elements of order 6 will be some power of 4 - not 4^2 (because (4^2)^3 = 4^6 = 1 mod 13, so it has order 3), not 4^3 (it has order 2), not 4^4 (has order 3), but 4^5 is fine. Basically - any number relatively prime to 6 (1 or 5) will give you an exponent that will give you another remainder mod 13 of order 6.

Say, for another example, you want to find elements of order 10 modulo 31. You find 15 works. Then 15^1, 15^3, 15^7, and 15^9 will give you all elements of order 10 mod 31.

Q:How many polynomials

of degree k with coefficients 0 and 1 don't have exactly two roots?

Can such a polynomial have more than two roots?

A: The polynomial can't have more than two roots (there are only two residues, 0 and 1, modulo 2).

As for the number of polynomials f with exactly two roots, the condition is f(0)=0 and f(1)=0. This translates to conditions a_k=0, 1+a_1+...+a_k=0, giving a total of 2^{k-2} polynomials.

Q:Professor, for the midterm, should we expect questions similar to the format which we've been exposed to on our quizzes (suggested problems, etc.), or should we prepare ourselves for proofs, and questions of this nature? Thanks for your time!A: There are three questions that start with "show ..." But these are questions of the same format that appeared in suggested problems (e.g. "show that if p>3 is a divisor of n^2+n+1 then p-1 is divisible by 3").Q:Could youpleasepost the solutions to the quizzes? I know some of the answers are below, but there are a few missing. Thanks!A: No, sorry. If you are not certain about one of the quesions, please ask here.

Q:For the midterm, it states that material up to primitive element theorem and its applications will be tested. However, does that mean material up to and including the primitive element theorem and its applications, or does that mean only up to?A: The test includes questions on primitive element theorem, order of an element and applications of primitive element theoremQ: Give a characterization of primes p for which the congruence x^4 + 1 = 0 mod p has at least one solution.A: If x^4=-1 mod p then x^8=1 mod p, so order of x is a divisor of 8, i.e. it is 1, 2, 4 or 8. But x or x^2 or x^4 =1 mod p contradicts x^4=-1 mod p, so order of x is 8. Thus 8|p-1.

Conversely, if 8|p-1, then let y be a primitive root mod p and let x=y^{(p-1)/8}. Then z=x^4=y^{(p-1)/2}= -1 mod p (because z^2=1 mod p, but z is not 1).

Thus the characterization is "those primes p for which p-1 is divisible by 8".

Q: Solve the congruence x^3 = 8 mod 13^3

A: x^3=8 mod 13 has 3 solutions: x=2, x=6, x=5 mod 13.

Consider first the case of x=2 mod 13.

Let x= 2 + 13 y. Then

So we want to solve

or equivalently

This means that y=0 mod 13, i.e. y=13z. This translates to

so z=0 mod 13.

Thus we get a solution x=2 mod 13^3.

Consider now the case x=6 mod 13. Let x=6+13 y. Then we want to solve

(the term with 13^3y^3 is not included, because it is zero modulo 13^3)

or equivalently

or

Since 16+3*36y=0 mod 13, this means 3-9y=0 mod 13 or y=-4 mod 13. Let y=-4+13z and get

or equivalently

or

so z=1 mod 13.

Finally x=6+13*(-4+13(1)) mod 13^3, i.e. x=123 mod 13^3

The case x=5 mod 13 can be considered in a similar fashion.

Q:(repost) Show that every prime divisor p>3 of n^2 + n + 1 is congruent to 1 modulo 6A: Let's compute the order of n modulo p.

If n=1, then n^2+n+1=3 and p=1 or 3, contradicting p>3.

So n is not 1.

If n^2=1 mod p, then p divides n^2-1=(n-1)(n+1). Hence n=1 or -1 mod p, and hence n^2+n+1=3 or 1 mod p, contradicting that n^n+n+1=0 mod p.

Finally n^3=n(n^2)=n(-1-n)=-n-n^2=1 mod p (we are using here that 1+n+n^2=0 mod p). Thus order of n mod p is 3 and hence 3 divides p-1.

Since p is also odd, it means that p=1 mod 6.

Q:Find all solutions of x^42 = 4 (mod 100)A: x^ 42=4 mod 100 if and only if x^42=4 mod 4 and x^42 = 4 mod 25.

For the first congruence x^42=0 mod 4 the solutions are x=0 or 2 mod 4, i.e. x=0 mod 2.

For the second congruence

noticethat x must be relatively prime to 25, so x^20=1 mod 25 by Euler's theorem. Thus the equation x^42=4 mod 25 is equivalent to x^2=4 mod 25, i.e. 25|x^2-4=(x-2)(x+2). Since (x-2) and (x+2) can't be simultaneously divisible by 5, this means that 25|x-2 or 25|x+2. Thus x=2 or -2 mod 25.Finally combine this with x=0 mod 2 to get the

answerx=2 or -2 mod 50 (equivalently x=2, -2, 48, 52 mod 100)Q:For this problem: x^3 = 8 (mod13^3). I started by trying to solve x^3 = 8 (mod 13) and got x = 2,5,6 (mod13).From here, I used the method shown in class for each of x = 2,5,6 to arrive at 3 solutions for x^3 = 8 (mod13^3).

Namely, x = 2, -125, 123 (mod 13^3).

Is this the only method of doing the question, or are there any less "tedious" ways?

A: This is the right method. Unfortunately I am not aware of a less tedious method.

Q:Show that every prime divisor p>3 of n^2 + n + 1 is congruent to 1 modulo 6A: Hint: To show that p-1 is divisible by 3, show that the

orderof n modulo p is 3. Let me know if you need a more complete answer by reposting this question on the top.Q:How many polynomials

of degree k with coefficients 0 and 1 don't have any roots modulo 2?

A: The condition is that f(0)=1, f(1)=1 mod 2. The first condition is equivalent to a_k=0 mod 2. The second condition is equivalent to a_1+a_2+...+a_k=0 mod 2. Thus we can choose a_1,...,a_{k-2} in an arbitrary manner and a_{k-1} mod 2 is determined, while a_k=0 mod 2. Thus there are 2^{k-2} such polynomials.Q: How many solutions does the congruence 1+x+...+x^23 = 0 (mod111) have?A: Since 111=3x37, the congruence 1+x+...+x^23=0 mod 111 is equivalent to the system of two congruences 1+x+...+x^23=0 mod 3 and1+x+...+x^23=0 mod 37.

The first of these has 2 solutions x=1 or -1 mod 3 (just try 0, 1 and -1).

For the second equation, notice that 1+x+...+x^23=0 mod 37 is equivalent to (1-x)(1+x+...+x^23)=1-x^24=0 mod 37 and x is not congruent to 1 mod 37. The number of solutions of x^24=1 mod 37 is gcd(24,36)=12. Since x=1 is one of the solutions and we want to exclude it, we get 11 solutions of 1+x+...+x^23=0 mod 37.

By CRT we get 2x11=22 solutions for the original congruence modulo 111.

Q:find all solutions to x^7 is congruent to 15 mod 137

A: 136=8*17, so 7 is invertible modulo 136. Find the inverse s and the answer is 15^s mod 137.(s=39, 15^39=121 mod 137)

Q:find all solutions to x^17 is congruent to 0 mod 137

A: 137 is prime, so 137|x^17 if and only if 137|x.Q:if 2^n-1 is prime prove n divides 2^n-2

A: For k<n, 2^k<2^n-1.Since

this shows that order of 2 mod 2^n-1 is exactly n. Thus n divides (2^n-1)-1=2^n-2.

Q:Show that 4 is not a primitive root modulo any prime p.

A: If p is odd, then since 4=2^2,and thus the order of 4 is smaller than p-1.

If p=2, then 4=0 mod 2 and hence is clearly not a primitive root.

Q: How many solutions does x^51 = 1 (mod 137) have.Note: I solved that x^17 = 1 (mod 137) has 17 solutions. Hence

x^51 = 1 (mod 137) must have at least 17 solutions as well. I am trying to use the fact that there is no x with order 51 to prove that every x st

x^51 = 1 (mod 137) must also satisfy x^17 = 1 (mod 137), hence if this holds then that means it will also have 17 solutions.

Is this the correct approach? Please provide some clues, thank you!

A:You could do it that way indeed: if x^51=1 mod 137, the order of x mush divide both 51 and 136, hence it must be 1 or 17. In any case x^17=1 mod 137. Conversely if x^17=1 mod 137, then x^51=1 mod 137.

An

alternativeway: if x^51=1 mod 137, then x^17=1^s=1 mod 137 where s is the inverse of 3 mod 137.Yet another

solution:so first you notice that the congruence

has 17 solutions and then for each solution y the congruence

has only one solution

(because 3x91 = 1 mod 136)

Q: In class we covered the problem x^2 + ax+ b = 0 (mod p). Could you re-explain this example with emphasis on(i) Why you divided the cases into p=2 and p does not equal 2

(ii) The case when p=2, it suffices to solve x^2 = 0, x^2 + x =0, x^2+1 =0, x^2+x+1=0.

A: (i) The trick with completing the square, or, equivalently, the formulaworks only if we can divide by 2. If p is equal to 2, we can't do it, so we have to consider p=2 separately.

(ii) If p=2, the coefficients a, b could only be 0 or 1 mod p. Thus there are only 4 equations to solve and each one of them is easily solvable.

Q: Could you please provide a list of which chapters from the textbook we have covered? Thanks！A: We covered 1,2,3,5,6,8,9,10,11,12,16,17,18,19,20,21,22,part of 23,part of 24Q: From the question that was solved belowThe solution was x = 3. Why do we not include x = 3 * (k * 7 + 1), k>=1 as other solutions to the congruence?

A: The answer iswhich is equivalent to saying x=3+21 k for any integer k.

Q：How many solutions does the congruence x^40= 1 (mod100) have?

A: Since x^40=100m+1, it means that gcd(x,100)=1 (because 1 is divisible by gcd(x,100)).If x is relatively prime to 100, then x^{\phi(100)}=1 (mod 100). \phi (100)= (4-2)(25-5)=40.

So x is the solution of x^40=1(mod 100) if and only if x is relatively prime to 100.

There exactly \phi(100)=40 distinct (modulo 100) numbers that are relatively prime to 100.

Answer:The congruence has 40 solutionsQ:N=pq, where p and q are distinct primes.there exist x and y, such that x*2=y*2 mod N, but x is not congruent to y mod N, and x is not congruent to -y mod N. find p and q.

A: It's impossible to determine p and q: one can have x=y mod p and x=-y mod q for any distinct p and q.Q:How many solutions does the congruence x^40 is congruent to 2 mod100 haveA: This congruence doesn't have a solution. If x^40=2 mod 100, then x is even, but then x^40 is divisible by 4 so can't be equal to 2 mod 100.Q:I was wondering if you could provide the answers for 18.2 please.18.2 (a) Show that in fact RSA decryption does work for all messages a, regardless of whether or not they have a common factor with m.

(b) More generally, show that RSA decryption works for all messages a as long as m is a product of distinct primes.

(c) Give an example with m=18 and a=3 where RSA decryption does not work (remember, k must be chosen relatively prime to phi(m)=6).

Parts (a) and (b) are similar to 17.4 which asks to show that b^u as found by Algorithm 17.1 is still a solution for "x^k is congruent to b mod m" if gcd(b,m)>1 but m is a product of distinct primes. u is a solution to ku-phi(m)v=1.

A: a,b) Let N=p_1p_2 ... p_n for distinct primes p_iRSA algorithm starts with message a and outputs a^{ks} mod N where ks = 1 mod phi(N).

The message a could be divisible by p_i or not divisible by p_i. If it is, then a^{ks}=0=a mod p_i. If a is relatively prime to p_i, then a^phi(N)=1 mod p_i, since phi(N) is divisible by p_i - 1. In particular a^{ks}=a mod p_i. Thus regardless of what a is, a^{ks}=a mod p_i for all i and hence a^{ks}=a mod N by CRT.

Q:Feb 07:Solve the congruence x^2+x-1=0 mod 11A: 11 is a prime number, so we can divide. x^2+x-1=(x+1/2)^2-5/4=0 (mod 11). 1/4=3 (mod 11), so (x+1/2)^2=4 (mod 11), so x+1/2=2 (mod 11) or x+1/2=-2 (mod 11). 1/2=6 (mod 11), so x=3 (mod 11) or x=7 (mod 11)Q:general question about fermat: does p have to be necessarily prime?consider: 7^5=1 mod6, 6 is not prime, only that 7 and 6 are co-prime. please advise, thx.

A: Fermat's little theorem guarantees thatifp is prime, then a^(p-1)=1 mod p for all a not divisible by p. It doesn't say anything about whether for a composite number n the equality a^(n-1)=1 mod n holds for some particular values of a. In your example 7^5=1^5=1 mod 6, but the reason has nothing to do with FLT (it has to do with the fact that 1 raised to any power is still 1).Q: 9.4 a) from jan 26:is true, prove m=1734251

is composite.

it cannot be sufficient to simply state that since 7*1734250 is not congruent to 1 modm, m is not prime?

A: If m is prime, then by FLTSince this equality doesn't hold, m is not prime.

Q:Find a multiple of 77 that ends with 999attempted:

77x=999mod1000 (subtracting 999 from that multiple would leave 3 0s)

but

cameup with x=12987; clearly wrong, please correct!A: 12987*77=999999Q:find the non-negative solutions of 7x+19y=1A: if x>0 or y>0 then 7x+19y>1. If x=0 and y=0, then 7x+19y=0. Thus there are no non-negative solutions of this equation.

Q:Show that the congruence

x^2 = a (mod21)

can have 0, 1, 2 or 4 solutions depending on a

I tried to show this by using CRT: since 21 is the product of 3 and 7, I worked with two congruences

(1): x^2=a(mod3) and

(2): x^2=a(mod7)

then showed that both congruences can have 0, 1 or 2 solutions (depending on a) (by solving for a= 0, 1, 2 for (1) and a = 0, 1, 2, ..., 6 for (2)), which

implied that (3): x^2=a(mod 3*7=21) has 0, 1, 2, or 4 solutions (depending on a) (since multiplying the number of solutions for (1) and (2) with the same value of a gives the number of solutions for (3)).

Is this correct or are there any less tedious methods?

A: This is correct.We have recently learned a theorem that equation of degree n has at most n different roots modulo a prime p, which shows immediately that x^2=a mod 3 and x^2=a mod 7 each have 0,1 or 2 solutions, but without using it what you did is indeed the best way.

Q1Find 2^220 (mod 221) Conclude that 221 is composite.A: Use successive squaring:

2^220=4^110=16^55=16*256^27=16*35^27=16*35*1225^13=16*35*120^13=16*35*120*14400^6=16*35*120*35^6=16*35*120*120^3=16*35*120*120*35=16 mod 221

If 221 were prime, then 2^220 would have been 1 mod 221 by FLT. Hence 221 is composite.

Q2Show that a^48=1 (mod 221) for all a relatively prime to 221.A: 221=13*17

a^48=a^(12*4)=1 mod 13 by FLT

a^48=a^(16*3)=1 mod 17 by FLT

Thus a^48=1 mod 221 by CRT

Q:Solve the congruence

(*)

A: if x is the solution of (*) we have x^7=3(mod 7), x^7=0(mod 3) so 3|x.

y^6=1(mod 7) for all y that are coprime with 7. So (since our x is clearly coprime with 7)

x^7=x^6*x=x=3(mod 7). So x=0(mod 3) x=3 (mod 7) but chinese remainder theorem

the solution mod 21 is unique and 3 is clearly the solution.

Q: According to Feb 2 lecture, X^24 = 1 (mod 35) has phi(35) = 24 solutions. Why is this?

A: By the Euler theorem any x such that (x,m)=1 satisfies

So for m=35 phi(35)=(5-1)(7-1)=24 so any x that is coprime (and there exactly 24 such x mod 35) with 35 is a solution of x^24=1 (mod 35)

if x is not coprime with 35 then it can't be the solution because (1,35)=1.

Q:

A: 6= (-1) (mod 7),

6x=(-x) (mod 7),

6x=-x=5(mod 7)

x=-5 (mod 7)

x=2 (mod 7)

Q: 11.1 b) Determine the value of

A:

Q: 11.5 Find x that solves

and

A: We should solve

x=3+37k, x=1+87m, or, equivalently, 3+37k=1+87m, i.e. 87 m - 37 k = 2.

Rewrite this as 13m - 37 (k - 2m) = 2 and let k'=k-2m. Rewrite 13m - 37 k' = 2 as 13(m-3k') + 2 k' = 2. One solution is m-3k'=2, k' = - 12. Thus m= -34, k=k'+2m = -80.

Thus x=3+37 k = 3 - 37*80= - 2957.

(This is only one possible solution. Other ones are given by -2957 + 87*37 t with integer t).

Q: Show that for

the congruence

holds for every a relatively prime to m.

(Hint: use Fermat's little theorem to compute a^{m-1} mod p for every prime divisor p of m).

A: This was shown in class Tuesday, January 31.

Q:Find the remainder when a is divided by m (a) a=207^321+689! m=7(b) a=(123)(45)(678)(910)(112) m=6

A: a) 689! is divisible by 7.207=(-3) mod 7 and (-3)^6= 1 mod 7 by FLT. Thus 207^321 = (-3)^(53*6+3)= (-3)^3 = 1 mod 7.

b) 678 is divisible by 6, so the whole product is also divisible by 3.

Q:For the following two questions:9.4 a) Assuming that the congruence

holds, show that 1734251 is a composite (i.e. non-prime) number.

c) The congruence

is true. Can you conclude that 52633 is a prime number?

Is it enough to just show by using Fermat's little theorem?

A: In a) FLT shows that 1734251 is composite.In c) FLT doesn't show anything.

Q:8.4 (d) Show that a number is divisible by 9 if and only if its sum of digits is divisible by 9.A: Let the number bei.e. the digits are a_0,a_1,...,a_n.

Then

This shows that the remainder of division of the number by 9 is the same as the remainder of division of its sum of digits by 9.

Q:based on 2.1 (b) Show that in a primitive Pythagorean triple a,b,c exactly one of a,b,c is divisible by 5.A: Modulo 5 all the squares are congruent to 0 or plus/minus 1. If a^2+b^2=c^2 mod 5 and (a,b,c) is not (0,0,0) mod 5, the only options areIn each of these cases exactly one of a,b,c is equal to 0 mod 5.

Q:Find all integer solutions of the equation 65432 x + 98765 y = gcd(65432,98765)A: 98765=65432+33333, so we rewrite this equation as 65432 x' + 33333 y = gcd (65432, 33333) with x'=x+y.Next 65432 = 2*33333-1234, so we rewrite the equation as -1234 x' + 33333 y' = gcd ( -1234, 33333) where y' = y+2x'.

Next 33333 = (-27)*(-1234) + 15, so we rewrite the equation as -1234 x'' + 15 y' = gcd ( -1234, 15) where x''=x'-27y'

Next -1234 = (-82)(-15)-4, so we rewrite the equation as -4 x'' + 15 y'' = gcd(-4,15) where y''=y'-82x''

Finally 15 = (-4)(-4)-1, so we rewrite the equation as -4x''' - y'' = gcd(-4,-1)=1, with x'''=x''-4y''.

One solution of this equation is x'''=0, y''=-1, i.e. x''=-4, y'=y''+82x''=-329, x'=x''+27y'=-4+27*(-329)=-8887, y=y'-2x'=-329+2*8887=17445, x=x'-y=-8887-17445=-26332.

All other solutions are given by x=-26332 + 98765 k, y=17445 - 65432 k, k - any integer.

Q: Find 10^5^101 (mod 21)A: 10=1 mod 3, so 10^5^101 is 1 mod 3.By FLT, 10^6=1 mod 7. Now we want to divide the exponent 5^101 by 6 with remainder. We see immediately that 5^101=(-1)^101= -1=5 mod 6. Thus 10^(5^101)=10^(6q+5)=10^5 mod 7.

Finally 10^5=3^5=5 mod 7.

Combining these two

resultsusing CRT we find that 10^5^101=19 mod 21.Q: Find a numberwith

A: 73 is a prime number, so by FLT 9^72 = 1 mod 73. Now 794=11*72+2, so 9^794=9^2=81=8 mod 73Q.Show that for a prime number p the number (p-1)!+1 is divisible by p(Hint: consider the number (p-1)! mod p. In this product one can split most of the residues to pairs of a residue and its inverse).

A: In the product

every residue comes with its inverse modulo p. In general these two residues x and x^{-1} are different from each other, except when x=x^{-1}, or, equivalently, x^2=1, i.e x=1 or -1.

Thus (p-1)!= -1 mod p.

Q.Does

x^10+y^10 = 11z^10

have non-zero solutions mod 6?

could it be shown using mod 6 instead of 4 from the answer below?

A: For a non-zero x, x^2=1,4,3 mod 6, so x^10=1,4,3 mod 6. Same holds for y^10. 11z^10 is 5,2,3 mod 6.So 1^10+4^10=11*1^10 mod 6 is a non-zero solution mod 6.

So I don't see an obvious way of concluding non-existence of non-zero solution by trying to do it mod 6 instead of mod 4.

Q.Determine the value of 2^2012+3^3013(mod7)A:Compute first 2^2012 mod 7.

2^3=1 mod 7, so 2^2010=1^670=1 mod 7 and so 2^2012=4 mod 7.

Now 3^6=1 mod 7. Apply this to compute 3^3013 mod 7 in the same way: 3^3013=3^3012 * 3 =3 mod 7.

Thus 2^2012+3^3012 = 0 mod 7

Q:2.6) b) Find a Pythagorean triple (a,b,c) with c=a+2 and c>1000.c) Find all primitive Pythagorean triples (a,b,c) with c=a+2.

A: a^2+b^2=(a+2)^2 means 4a+4=b^2. This equation has a solution for every even number b: b=2k, a=k^2-1. If k is odd, a is even and the triple (a,b,a+2) is not primitive. However if k is even, then gcd(k^2-1,k)=gcd(-1,k)=1, so gcd(k^2-1,2k)=1 and thus the triple is primitive.

In short all the primitive solutions are of the

form(k^2-1,2k,k^2+1) with even k.Q: SolveA:So the solutions are 3 and -3 mod 7.

Q: Show that there are infinitely many primes of the for 6n+5.A: First notice that every prime number, except 2 and 3 is congruent to either 1 or -1 mod 6.Consider the number 6n!-1. All its divisors are at least n and among its prime divisor at least one must be congruent to -1 mod 6 (because the product is congruent to -1 mod 6).

Q:Show that the equationhas no non-zero integer solutions.

A:We can assume gcd(x,y,z)=1

Let's

lookat the remainder of the both sides modulo 4.so x^{10}+y^{10} mod 4 can be 0 (if they are both even), 1 or 2

11z^{10} mod 4 can be 0 (if z is even) or 3.

But

x^{10}+y^{10}=11z^{10}, so both sides are 0 mod 4 and x,y,z are all even,

that condradicts with the assumption gcd(x,y,z)=1.

Q: (2.3) Which odd numbers a can appear in a primitive Pythagorean triple (a,b,c)?

A:Any odd a can appearQ:Which even numbers b can appear in a primitive Pythagorean triple (a,b,c)?A:If b is not divisible by 4 it cannot appear in the Pythagorean triple.

Let's look at the remainders of both sides modulo 8.

a, c are odd so their squares can be only 1 mod 8. If b is not divisible by 4

b^2 mod 8 is 4, so a^2+b^2 mod 8=5 that is not equal to one.

If b is divisible by 4 take b=2^{k}d, where d is odd. We know that k>1.

Then take the Pythagorean triple a=2^{2k-2} - d^{2}, b, c=2^{2k-2} + d^{2}.

Since k>1 a is odd.

gcd(a,b,c)=1 (assume the contrary, there exist prime p that divides a,b,c. Since a is odd p is odd. Odd prime p divides b, so it must divide d, so p must divide a+d^{2} that is a power of two. contradiction).

So we constructed a primitive Pythagorean triple with the given b.

Q: (2.1)We showed that in any primitive Pythagorean triple (a,b,c) either a or b is even. Use the same sort of argument to show that either a or b must be a multiple of 3.A: Consider the identity a^2+b^2=c^2 mod 3. If neither a nor b are divisible by 3, then

and similarly for b^2. Thus a^2+b^2 = 2 mod 3, which is not a square of anything mod 3.

Thus either a or b must be divisible by 3.

Q: Show that the equation x^2 + x = y^2 has no non-zero integer solutionsA:Since x, (x+1) can't have common divisors if some prime p divides x, then p^2 divides x (since p divides y, so p^2 divides x(x+1) and gcd(x+1,x)=1). So

for some integer a. For the same reason

for some integer b. But it means that we got two plus/minus squares of integers with the difference one, so x=0 or x=-1.

Q: Show that if x, y,z have no common factors and satisfy the equation above (x^2 + 2y^2=z^2)Then one can find integers s,t such that either z-x=2s^2, z+s=t^2 or z-x=s^2, z+x=2t^2.

A:First of all notice that x,z must be odd (if x is even, z is also even and it follows easily that y must be even as well).Now rewrite the equation as 2y^2=x^2-z^2=(x-z)(x+z).

Notice that gcd(x-z,x+z)=gcd(x-z, 2x)=2gcd(x,z)=2.

Thus the only common factor of (x-z) and (x+z) is 2.

It follows that all the exponents of the primes other than 2 in the factorizations of x-z and x+z are even. The exponent of 2 is even in one of them and odd in the other one.

Thus either x-z=2s^2, x+z=t^2 or x+z=2s^2, x+z=t^2.

The required parametrization follows.

Q: Solve the equation x^2 + 2y^2=z^2 in integers.A: See question above.

Q: (2.4)In our list of examples are the two primitive Pythagorean triples

Find at least one more example of two primitive Pythagorean triples with the same value of c. Can you find three primitive Pythagorean triples with the same c? Can you find more than three?

A: I am sorry for assigning this question: it seems a bit tougher than I expected it to be.

One possible approach to it is to use the following identity:

(we will later learn how this identity naturally appears from some basic properties of complex numbers).

This identity allows you to get a representation of some numbers as sum of two squares in two different ways.

To get a representation of a number as a sum squares in four different ways, use this identity twice:

and now use the identity once again.

Q: Show thatfor any natural numbers m,n.

A:We showed in class that ifthen

Let's now divide n by m with remainder: n= qm+r. By applying the result above q times, we get that

So if we want to compute gcd(10^x-1,gcd^y-1), we can always replace the pair of parameters (x,y)=(n,m) by the pair (x,y)=(m,r) without changing the answer.

We know from what we have discussed about Euclid's algorithm that we can repeat this procedure until we get to the pair (gcd(m,n),0). For this pair the value of gcd(10^x-1,10^y-1) is

Q:Find an integer solution ofwith a>1000 and with a, b, c having no common factor.

A:Let x=a/c, y=b/c. Then we want to find a rational solution x,y to the equation x^2+xy+y^2=3. One solution is x=1, y=1.We showed in class that all rational solutions of such equation are given by intersecting the quadric with lines of the kind y-1 = m(x-1) with rational m. Plugging the value of y from the equation of the line into the equation of the quadric we find

x^2+x(mx+1-m)+(mx+1-m)^2=3, or, equivalently, (1+m+m^2)x^2+(1-m+2m(1-m))x+(1-m)^2-3=0.

One solution of this equation is x=1, so the second solution is

and

It remains to choose a large enough m so that the numerator and denominator in the fractions will be large enough, e.g. m=50 that gives a=2398, b= - 5099, c= 2551 (check that these are relatively prime!) .

Q: January 10 question1Prove that

has no nonzero solutions

A: We can assume that gcd(m,n)=1, otherwise writethen

Now m_1 is divisible by three, so

is divisible by 9, so n_1 is divisible by three. We get the contradictionh with the fact that

Q: January 10 question4Prove that if

and x,y,z have no common factors, then x and z must be odd and y must be even.

A: Assume x is even, thenis also even, so z is even and

is divisible by 4, so y is even and x,y,z have the common factor 2.

So x is odd and so is z (as a sum of odd and even number). Now if x,z are both odd then

is divisible by 4 and so y is even.

Q: January 10 question3prove

has no solutions with x and y both odd

A: If x is odd, z must be odd as well. Let x=2k+1, y=2n+1, z=2m+1 the equation translates into 4k^2+4k+8n^2+8n+3=4m^2+4m+1. The left side gives remainder of 3 when divided by 4, while the right side gives remainder of 1. Thus no solution with odd x, y could possibly exist.Q:Show that

is irrational. (Hint:

A:Applying the hint we find that

satisfies the equation

or, equivalently, 8x^3-6x-1=0. By a theorem we proved in class the only candidates for rational solutions of this equation are

By

checkingeach one of these we find that the equation has no rational solutions, so x must be irrational.Q: Find at least one integer solution to the equation 21x - 13 y = 1A: Write the equation as 8 x + 13 (x-y) =1, let y'=x-y.Now solve 8x + 13 y' = 1

Write it as 8 (x+y')+5 y' = 1

Let x'=x+y'

Solve 8x'+5y'=1

Write it as 3x'+5(x'+y')=1

Let y''=x'+y'

Solve 3x'+5y''=1

Write it as 3(x'+y'')+2y''=1

Let x''=x'+y''

Solve 3x''+2y''=1, or x''+2(x''+y'')=1.

One solution: x''=1, x''+y''=0, i.e. x''=1, y''=-1.

Now unwind the substitutions: x'=x''-y''=2

y'=y''-x'=-3

x=x'-y'=5

y=x-y'=8.

Thus one solution is x=5, y=8 (check: 21*5-13*8=105-104=1).

All other solutions are of the

formx=5+13k, y=8+21k.Q: Please provide some hints on how to do the second problem for January 10th:Show that the equation x^2+x=y^2 has no non-zero integer solutions

Hint: If you want to show that something (x^2+x) is not a square of an integer, try to prove that itcan't fit into the "gap" between two consecuitive squares.

A hint to a different solution: rewrite the equation in the formand use that x, x+1 are relatively prime.

Q: Show that ifis a rational number, then it is an integer.

A: If n=a^2/b^2 for some integers a, b, then nb^2=a^2. Let p be any prime number and let k_a, k_b, k_n denote the multiplicities of this prime in the prime factorizations of a, b, n respectively. The equality nb^2=a^2 and uniqueness of factorization to primes tells us then that k_n + 2 k_b = 2 k_a. Thus k_n is even.Hence the prime number factorization of n is of the form

and hence square root of n is integer.

Introduction to Number Theory

Introduction to Number Theory

(\pm 1)^2,(\pm 2)^2,

(\pm 3)^2,(\pm 4)^A,

Q:if n is an integer s.t n > 1 then n does not divide (2^n) - 1A:suppose p is the smallest prime divisor of n in the factorization of n into distinct primes then gcd (n , p - 1) = 1 hence there are integers k and ssuch that n(s) + k(p - 1) = 1. now suppose p divides (2^n) - 1 then 2^n = 1 mod p and since p does not divide 2 then 2^( p - 1) = 1 mod pbut 2 = 2^( n(s) + k( p - 1)) = (2^ n)(s)) ( 2^( p - 1)(k)) = 1 mod pcontradictionhence p does not divide (2^n) - 1 and since p is the smallest divisor of n, n does not divide (2^n) - 1Q: prove a^(2^n) = 1 mod 2^(n + 2) where a is oddA:suppose a is odd then a = 2k + 1 k integer now 2^n = 2( 2^(n-1)) hence a^(2^n) = (a^2)(2^(n -1)).now 2^(n + 2) = 4(2^n) and a^2 = 4k^2 + 4k + 1 hence a^2 = 1 mod 2^(n + 2)a^2(2^(n - 1)) = 1^(2^(n - 1)) = 1 mod 2^( n + 2)hence a^(2^n) = a^2(2^( n - 1)) =1 mod 2^( n + 2)how do you approach a question like 3x^2 + 5x +1=0 mod 199(prime) ?this is what i tried: made 5x as 204 which would be divisible by 3...then by some algebra and completing the square, i ended up with (x+34)^2=28 mod199i checked if 28 was QRmod 199..it was, then i got y^2=28 mod199. where y=x+34 can't seem to continue to find a value for y since exponent 2 is not rel. prime with 198(phi199)..please advise, many thanks!Q; How to solve x^3 = 8 mod 13?Q: Is there going to be a particular emphasis on the material covered since the midterm or is it going to be evenly distributed throughout the whole course?Q: Is it possible to update the section on "What we actually covered?" just to be sure we don't leave out anything that we shouldstudyfor, orstudywhat we didn't cover? Also, in regards to Lecture 19 (not on exam)..what *date* was it taught? Just toconfirm.Q:prove y^2 = x^3 + 7 has no integer solutionsA:suppose ( x , y) is a integer solution such that x is even then let x = 2k then x^3 + 7 = 4(2k^3) + 7 hence y^2 is odd.let y = 2j + 1 then y^2 = 4(j^2 +j ) +1 = 4(2k^3) + 7 and so dividing by 4 on both sides gives a remainder of 7 on one side and 1 on the other sidecontradiction and so x is odd.now y^2 + 1 = x^3 +8 = ( x +2 )( x^2 -2x + 4)since x is odd x^2 - 2x + 4 = 3 mod 4. Now suppose q is prime such that q = 3 mod 4 and q does not divide x^2 - 2x + 4then x^2 -2x + 4 is not equal to m( 3 + 4r ) for r,m integers contradiction since x^2 - 2x + 4 = 3 mod 4. There is a prime q such that q dividesx^2 - 2x + 4.now consider y^2 + 1 = x^3 + 8 mod qhere q divides x^3 + 8 since q divides x^2 -2x + 4 and so y^2 + 1 = 0 mod q and so -1 is a QR mod q then since q is odd (-1)^(q-1)/2 = 1 mod qby Eulers criterion but (q-1)/2 = 1 + 2p hence (-1)^(q-1)/2 = -1 contradictionHence y^2 = x^3 + 7 has no integer solutions (Anthony)Q:Show that the equation x2 ≡ a mod 21 has either 1, 2 or 4 solutions modulo 21.

Q: are there any tricks of factoring Gaussian integers like 1+3i and 3+4i? other than by trial and error?Q: For the proof of the question "If A Gaussian integer Z is a Gaussian prime, then N(Z) is a prime or a square o a prime of theformp=4k+3", we have the following sentence from theanswerbelow: " If z is not an integer then z divides aproductof primes in the integers." Can someone explain why we have this causation?A:Here z divides aproductof primes in the integers because (z) ( conjugate of z) = N( z ) and soby the unique factorization in the guassian integers z must divide a prime in the Integers( Anthony)studyfor, orstudywhat we didn't cover? Also, in regards to Lecture 19 (not on exam)..what *date* was it taught? Just toconfirm.Q: I know you said that Pell's Equation won't be on the exam; does this mean that nothing from chapters 30-32 from the textbook is going to be on the exam? Also, just toconfirm, since the midterm we have covered chapters 23-27, 33, and 34 - is this correct?Q:How can we find thatx^25 = 1 mod 11, x /= 1 mod 11 and x^25 = 1 mod 43, x /= 1 mod 43 each of these congruences has 4 soultions

Q:What is Unique Factorization in Gaussian Integers?A: This analogue of Fundamental Theorem of Arithmetic, but for Gaussian integers.

A Gaussian integer p is called prime if whenever p | ab then p|a or p|b.

Now unique factorization for Gaussian integers says that given any Gaussian integer N can be factored into primes. For example in Gaussian integers 2=(1-i)(1+i)

Q: prove the only integral solution to y^2 = x^3 + x is x = 0 and y = 0A:suppose x^3 + x = y^2 now note x^3 + x = x( x^2 + 1) then note that x and x^2 + 1 are relatively primeand so x^2 + 1 and x are squares since the product is a square.let k^2 = x^2 +1 then k^2 - x^2 = (k - x)(k + x) = 1hence by the fundamental theorem of arithmetic in the integers k - x = 1 and k + x = 1or k - x = - 1 and k + x = -1 and so k = 1 or -1 hence k^2 = 1 and so x = 0 and y = 0Q: could someone help out with this: x^3 + 4x + 8=0 mod 15? thanks!A:there are no solutionsbreaking up 15 = 5(3) check mod 3x^3 + 4x + 8 = 0 mod 3here the equation has no solutions in mod 3 and so has no solutions in mod 15.(Why Not?)let x=2, the 2^3 + 4*2 + 8 = 8 + 8 + 8 = 24 = 0 (mod 3), so by CRT, it does not matter what mod 5 is, you can get a solution 0 mod15.Q:What is Sum of two Square Theorem?A:the sum of 2 squares theorem for prime numbers states if p is a prime then p can be written asthe sum of 2 squares ie ( p = a^2 + b^2 ) for a , b integers iff p = 1 mod 4.Q:What is Unique Factorization in Gaussian Integers?Q:Why doesn't this equality contradict uniqueness of factorization to prime factors in Gaussian integers?

A: 5 * 5 = (3 + 4i)(3 - 4i) = (2 - i)^2 (2 + i)^2

Q:Factor 65 as a product of Gaussian primes

A:

65 = 13(5) = (2+ i)( 2 - i)( 2 - 3i )( 2 + 3i )

Q:Find all the solutions of the equation

A: (assuming we are looking for integer solutions) This factors as (x+3y)(x-3y) = 1, and since we are looking for integer x and y, the factors x+3y and x-3y must also be integers. Then by factoring 1, we must have x+3y = 1 and x-3y = 1, or x+3y = -1 and x-3y = -1. In both cases, we find y = 0, and either x = 1 or x = -1. So the two integer solutions are (1,0) and (-1,0).

Q:Find all the solutions of the equation

A: This is a standard Pell's equation. See theorem 32.1 in the textbook. In this case D=5. The procedure for solving such equations is as follows: first find the solution (x_1, y_1) with smallest x_1 by continued fractions (theorem 40.4 in the textbook). Then all the solutions are obtained by taking powers of (x_1, y_1).

sqrt(5)=[2,overbar(4)], (Proposition 40.1 for example). Then p/q=[2,4]=9/4. m=1 is even (for this question), so the desired smallest solution is (9,4).

QFind infinitely many solutions of the equation

(there is no need to find all the solutions)

A: Take a look at exercise 32.1(d) in the textbook. It tells us that one can obtain the solutions to x^2-Dy^2=M (*) by first finding one particular solution to (*) and then combining it with solutions of x^2-Dy^2=1 in a certain way. One particular solution to x^2-5y^2=11 is (4,1) for example.

QFactor the Gaussian integer 5+15i into a product of non-unit Gaussian integers which can't be further factored as products of

non-unit Gaussian integers.

A:

5 + 15i = (1 - i)*(1 - 2i)^2 (1 + 2i)

Q:a) Suppose that N(z)=p^2 for a Gaussian integer z and a prime number p. Show that if p=4k+3, then z is a Gaussian prime. Show that if p=4k+1, then z is not a Gaussian prime.

A:

a)

suppose N(z) = p^2 and let p = 3 mod 4 such that z is not guassian prime then z has nontrivial factorization say z= (a+ib)(c + id) WLOG

then N(z) = (a^2 + b^2)(c^2 + d^2) = p^2

hence a^2 + b^2 = p and c^2 + d^2 = p and so p is a sum of 2 squares but p = 3 mod 4 and from the sum of two squares theorem p cannot be written as the sum of two squares

so z has trivial factorization hence z is guassian prime.

suppose p = 4k + 1 and let z be a guassian prime then conjugate of z is guassian prime and the product of z * (conjugate of z ) is the product of 2 guassian primes.

but N(z) = z * (zbar) = p^2 and since p = 1 mod 4 then p can be written as the sum of 2 squares and hence p is the product of 2 guassian primes and so p^2 is the product of 4

guassian primes contradiction.

NQ: (not a question, but) Proof that -1 is a norm inthat is, there is a solution to x^2+y^2 = -1 mod p.

There must exist some quadratic residue a^2 such that a^2+1 is a quadratic nonresidue modulo p (because if every QR + 1 is a QR, then since 1 is a QR, we must have 1,...,p-1 all QRs, contradicting the fact that there are only (p-1)/2 QRs). But since p = 3 mod 4, -1 is a quadratic nonresidue, so therefore -(a^2+1) is QNR x QNR = a quadratic residue (call it c^2). Thus

and so

as desired.

NA: Cool! (Yura)Q:Use uniqueness of factorization in Gaussian integers to show that there are no integer solutions of x^3 = y^2 + 1 with odd y.A: What I meant was "with y even".With y odd, the right side of the equation is 2 mod 4 and the left side of the equation is 0 mod 4.

So assume y is even.

Factor the right side of the equation as (y-i)(y+i). Now

Let's check whether y+i is divisible by 1+i:

Since y is even, this shows that y+i is not divisible by 1+i. Thus y-i, y+i are coprime.

Hence

for some units u,v. (Indeed, if x^3=mn with m,n relatively prime, then every prime factor of m appears with an exponent divisible by 3. Similarly for n).

Now let s=a+ib so that

Then

In particular comparing the imaginary parts we find that

i.e.

In particular either a or b is equal to plus/minus 1, while the other one is equal to 0. Thus s=a+ib is a unit, and hence y+i=u s^3 is a unit.

This is only possible for y=0, so we find the only solution x=1,y=0.

Q:how many solutions to the equation x^2 + y^2 ≡ 1 mod pA: If -1 is a quadratic residue modulo p, then we can solve the question as follows:

Let a be such that a^2=-1. Then

Make an invertible change of variables:

(the inverse transformation is given by

)

Then the equation becomes zw≡1 mod p and hence has p-1 solutions (for every non-zero z there is a unique w with zw=1 mod p).

If -1 is not a quadratic residue, the solution above fails.

In this case we can obtain a different solution using a trick with parametrization of the circle we used when discussing pythagorean triples:

If (x_0,y_0) is a solution of x^2+y^2=1 mod p different than (1,0), then the "line" through (1,0),(x_0,y_0) intersects x^2+y^2=1 mod p in two points. Indeed, the system of equations

has at most two solutions because it can be reduced to a quadratic equation modulo a prime number, and it definitely has two solutions ((1.0),(x_0,y_0)).

Conversely, if m is any residue modulo p such that

then the system

has two solutions: (1,0) and

Thus any residue m whose square is not -1 produces a solution and every solution besides (1,0) is obtained this way. Thus if -1 is not a quadratic residue mod p, there are p+1 solutions (p solutions corresponding to different values of m and the solution (1,0)).

So the

completeansweris as follows: if p=2, there are 2 solutions. If p=4k+1, there are p-1 solutions. If p=4k+3, there are p+1 solutions.Q:how many guassian primes are there of norm less than 11

A:there are no guassian primes of norm 0,1,3,4,6,7,8 or 10

the guassian primes of norm 2 are the following

1 + i , 1 - i , -1 - i , -1 + i

the guassian primes of norm 5 are the following

1 + 2i , 1 - 2i , -1 -2i , -1 + 2i , 2 + i , 2 -i , -2 - i , -2 + i

the guassian primes of norm 9 are 3, -3, 3i, -3i

hence there are 16 guassian primes of norm less than 11.

Q:suppose p is prime integer such that p = mn where m and n are guassian integers and are not units prove conjugate of m is equal to n.

A:suppose p is prime integer such that p = mn where m and n are not units and m = a+ ib then N(p) = N(m)* N(n) = p^2

hence N(m) divides p^2. Now since m is not a unit N(m) is not equal to 1 and so N(m) = p and so a^2 + b^2 = p

and so m* (conjugate m) = p.

but p = mn and so (conjugate of m) = n

Q:a Gaussian integer is a Gaussian prime if and only if N(z) is a prime or a square of a prime of the form p=4k+3.

A:

suppose N(z) is prime and z is not a guassian prime then z has a nontrivial factorization hence there is a guassian integer m which divides z

hence N(m) divides N(z) contradiction since N(z) is prime.

suppose z is a guassian prime now if z is an integer z cannot be equal to 2 or congruent to 1 mod 4 since it would then be of the form a^2 + b^2 and would be divisible

by a + ib.

If z is not an integer then z divides a product of primes in the integers. Then since z*(conjugate z ) = N(z) by the unique factorization in guassian integers z divides a

prime integer say p. Hence N(z) divides N(p) = p^2 and so N(z) = p hence N(z) is prime.

(this is what i think Anthony)

For the other part

suppose N(z) = p^2 where p = 3 mod 4 and suppose z is not a guassian prime then z has a nontrivial factorization say z = (a+ ib)( c + di) where neither of the

factors are units. N(z) = (a^2 + b^2)(c^2 + d^2) = p^2 and so a^2 + b^2 = p and c^2 + d^2 = p which implies p can be written as the sum of 2 squares contradiction

by the sum of two squares theorem.

Q:

If z is a guassian prime then N(z) is a square of a prime p where p is congruent to 3 mod 4

A: This is wrong: 2+i is a Gaussian prime of norm 5.

Q:Are there other solutions to q and r for which a=b(q) + r where a=48 + 27i and b = 1+2i and for which N(r) < N(b). Say, is r = 2 a valid solution?

A: Yes, the solution is not unique. Even in usual integers 5=2*2+1=2*3-1, so you have two choices for the remainder.Q:How many Gaussian integers are there of norm

120?A: Since 120=2^3 3^1 5^1, and the prime 3 (which is congruent to 3 modulo 4) appears to an odd degree, there are no such Gaussian integers.Q:Factor the number 7! as a product of Gaussian primes

A:First factor it as a product of usual primes:

Now factor these primes as products of Gaussian primes:

Q:let N(z) = p^2 where p is prime and z is a guassian integer if p = 3 mod 4 then z is a guassian prime

A:suppose N(z) = p^2 and let p = 3 mod 4 such that z is not guassian prime then z has nontrivial factorization say z= (a+ib)(c + id)

then N(z) = (a^2 + b^2)(c^2 + d^2) = p^2

so z has trivial factorization hence z is guassian prime.

(this is what i think Anthony)

Another solution: If

and p is congruent to 3 mod 4, then the factorization of

to Gaussian primes is p^2. Hence z=u p for a unit u. Hence z is a Gaussian prime.

Q:if p =1 mod 4 and N(z) = p^2 then z is not a Guassian prime

A: If p=1 mod 4, then p is a product of 2 Gaussian primes. Hence p^2 is a product of 4 Gaussian primes.If z is Gaussian prime, then the conjugate of z is Gaussian prime and hence

is a product of 2 Gaussian primes.

Thus if p =1 mod 4 and N(z) = p^2 then z is not a Guassian prime

Q:find Guassian integers q and r for which a=b(q) + r where a=48 + 27i and b = 1+2i and for which N(r) < N(b)

A:note that N(1+2i) = 5

consider r= -1 - i

48 + 27i - (-1-i) = 49 + 28i

[49 + 28i(1-2i)] / 5

= 21 - 14i

N(r) = 2 < 5

hence

the guassian integers q and r are the following

q = 21 - 14i

r = -1 - i

Q:When is -7 a square mod P?

A:For p which is not 2 and not 7

Thus it is 1 if and only if p is congruent to 1, 2 or 4 modulo 7.

Q:Compute

A:

(-32/101) = (-1/101) * (2/101)^5

now (2/101) = -1 since 101 is congruent to 3 mod 8

and (-1/101) = 1 hence (-32/101) = -1

Q:For what primes p the number 5 is a quadratic residue?Is p=2 a solution as well?

A:Yes, 5=1^1 mod 2.

Q:How many quadratic residues are there modulo 31?

why is theanswer(31-1)/2?A:There are 31 possible residues modulo 31: numbers from 0 to 30 represent all of them. Excluding 0 half the values are quadratic residues and half are quadratic non residues hence

the number of quadratic residues is (31-1)/2

Q:If

is prime, show that 3 is not a quadratic residue.

Combine this with the result of question 2 from March 1 to

conclude that every number not divisible by p is congruent to a power of 3 modulo p.A: To show that 3 is not a QR, that means (3/p)=-1

based on the formula, (p-1)/2 is

even, (3-1)/2=1 and "(p/3)=1 iff p=1". so (p/3)= -1 for surethen we show that 3 is not a QR.

From March 1st, we know that

"a is a quadratic non-residue modulo p if and only if a is a primitive root modulo p"

Then we can say 3 is a primitive root mod p

and by primitive element thm, every number which is not divisible by p is of the from 3^i for an unique "i" from 0 to p-1.

(This is what I think, Kevin Chen)

Q:Why are odd powers of primitive roots exactly the QNR?A: Let a be a primitive root modulo p. If the number x is a QR, then x=n^2 mod p. If n=a^i mod p, then x=a^(2i) mod p. Thus every QR is an even power of a. Conversely, even powers of a are clearly QR. Thus the remaining (odd) powers of a are the QNR.

Q：A:

Now (2/101)=-1 because 101=-3 mod 8

Hence

(14/101)=1

Q:Find infinitely many solutions of the equationx^2 - 5 y^2 = 11 (there is no need to find all the solutions)

How to solve such questions with RHS not equal to 1?

A: One solution is x=4,y=1.

Let now

(see solution of the question below for explanation of what is special about 9+4sqrt(5) )

Then x_k^2-5 y_k^2 = 11.

I am not really sure how to find all possible solutions of this equation.

Q: find the integer solutions to x^2-5y^2 = 1

A:

the integer solutions

the smallest positive integer solution where x and y is greater than zero is x=9 y=4

hence the other positive integer solutions are (x_k,y_k) such that

for integer non-negative k.

Q:Which lectures/questions will quiz 3 cover?A: Now posted on the main page.

Q:Let p = 2^n + 1 be a prime (n > 0). Show that a is a quadratic non-residue modulo pif and only ifa is a primitive root modulo p. The answer below says: "Let c be any primitive root modulo p. Then the other primitive roots are c^i with i relatively prime to p-1. In our case this means c is relatively prime to 2^n, which is the same as saying that c is odd. But odd powers of a primitive root are exactly the quadratic non-residues."Is this showing both directions of the if and only if?

A:

Yes: the odd powers of a given primitive root c coincide with both sets: the set of quadratic non-residues and the set of primitive roots mod p. Hence these two sets are the same.

Q:Show that any prime number p which is congruent to 1 modulo 6 is a divisor of some number of the formA:

let p be any prime

suppose p=1 mod 6. Notice that p is an odd prime. Now we want to show -3 is

a square mod p.

(-3/p) = (-1/p)(3/p)

= (-1/p)(-1)^(p-1)/2*(3-1)/2 (p/3)

= (p/3) since p is odd.

now since p=1 mod 6 we also have p=1 mod 3, hence (p/3)=1

hence (-3/p)=1, i.e. -3 is a square mod p. Thus n^2 = -3 mod p for some integer n hence p divides a number of the form n^2 +3.

Q: how many solutions are there to x^2- 9y^2 =1

A:

Integer solutions:

(x-3y)(x+3)=1

Hence x-3y = 1, x+3y=1 or x-3y= - 1, x+3y= -1. Hence x=1 or -1, y=0. There are two integer solutions.

(in rationals there are infinitely many solutions).

Q: If

Combine this (question 2 March 6) with the result of question 2 from March 1 to conclude that every number not divisible by p is congruent to a power of 3 modulo p.See below

By the question from March 1 this means that 3 is a primitive root modulo p. Thus every non-zero residue modulo p is a power of 3.

Q: For what primes p the number 5 is a quadratic residue?

A:

For p different from 5,

The quadratic residues modulo 5 are 1 and -1. Hence the answer is

Q: What are all the quadratic residues modulo 19.

A:

Hence quadratic residues are 1,4,5,6,7,9,-8,-3,-2.

Q: How many quadratic residues are there modulo 31?

A: (31-1)/2=15

Q: Show that the congruence

has a solution modulo any prime.

A:

let p be any prime

Here if x^2=-1 mod p or x^2=-2 mod p has a solution then -1 or -2 is a quadratic residue mod p.

if neither -2 or -1 is a quadratic residue then they are quadratic non residues. But (-2)(-1) = 2 is a product

of quadratic non residues and hence is a quadratic residue hence x^2= 2 mod p has a solution and so

(x^2+1)(x^2+2)(x^2-2) =0 mod p has a solution.

Q:Let a be a quadratic residue mod p and let p be an odd primeprove a is not a primitive root mod p

A:Suppose a is a quadratic residue mod p.

Since p is an odd prime and a is a quadratic residue, a^(p-1)/2 is congruent to 1 mod p by Euler's criterion.

This means that the

ordera is at most (p-1)/2, so a is not a primitive root.Q:Let a be a quadratic residue mod p and let p be an odd prime the integer p-a is a quadratic residue mod p if p=1 mod 4and is a quadratic non residue if p=3 mod4

A:suppose p is an odd prime and a is a quadratic residue mod p.

now (-1)^(p-1)/2 is equal to 1 when (p-1)/2 is even hence p-1 = 4k for some integer k and so p=1 mod4

(-1)^(p-1)/2 is equal to -1 mod p when (p-1)/2 is odd hence p-1= 4j +2 hence p=3 mod 4

Q:If p = 2^k + 1 is prime, show that 3 is not a quadratic residue.Combine this with the result of question 2 from March 1 to conclude that every number not divisible by p is congruent to a power of 3 modulo p.

A:If k>1 and k is even, then this number is equal to

so 3 is a quadratic non-residue modulo p.

If k=1, then p=3 and the question doesn't make sense.

If k is odd, then 2^k+1 = (-1)^k + 1 = 0 mod 3 and hence p is not prime.

Q:Let p = 2^n + 1 be a prime (n > 0). Show that a is a quadratic non-residue modulo p if and only if a is a primitive root modulo p.A:Let c be any primitive root modulo p. Then the other primitive roots are c^i with i relatively prime to p-1. In our case this means c is relatively prime to 2^n, which is the same as saying that c is odd. But odd powers of a primitive root are exactly the quadratic non-residues.Q:Show that 4 is not a primitive root modulo any prime p.my attempt:

Artin's conjecture: 2 is a primitive root modulo for infinitely many primes

if p odd:

then all primitive elements of p is in the form of 2^i, gcd(i,p-1)=1

2^2=4, gcd(2,p-1)=2 for all, thus 4 cannot be a primitive root modulo of any prime

if p=2,

4=0mod2; not a primitive root

is this correct?

A: no!

1) Artin's conjecture is still not proved.

2) It doesn't apply to all primes, only to infinitely many primes.

A solution has been posted below.

Q:how many primitive roots mod 19 exist? express them in powers of 2, 2 is one primitive root.

i tried phi(18) = 6, so there are six roots. 2 is given as one of them. will 5 7 11 13 17 be other roots since they are relatively prime to 18?

A: 2^5, 2^7, 2^11, 2^13, 2^17 are the other primitive rootsQ:Solve the congruence x^2+x-1 = 0 mod 1A: Complete the square:

Square roots of 4 modulo 11 are + or - 2. Thus x=-6 -2 = -8 = 3 or x=-6+2=-4 mod 11

1

Q:In the 2009 past midterm, question 1(b): "find all solutions to x^3 + 4x + 8 = 0 (mod 15)." We should start by looking at the same congruence mod 3 and mod 5, but how do you handle polynomials like this (especially since we can't factor or use our quadratic equation tricks)?A: 3 and 5 are very small numbers: just try all the possibilities. Small tricks: x^3=x for all x by FLT, so x^3+4x+8 = x+4x+8=2x+2 mod 3, so x=-1 mod 3.

x^3+4x+8=x^3-x-2=0 mod 5. x=-2,-1,0,1 ro 2 don't work, so there seem to be no solutions to this congruence.

Q:In class we said that CRT produces a unique solution, although at the same time we are using it as a tool to show that there are multiple possible solutions (eg, question1 quiz 2 and the question answered below 'How many solutions does the congruence 1+x+...+x^23 = 0 (mod111) have?'). Can you please clarify how we are using CRT in these cases.A: CRT guarantees that there exists only one solution modulo mn to a congruence of the form x=a mod m, x=b mod n if m and n are distinct.

If f is a polynomial, m,n are relatively prime and we try to solve f(x)=0 mod mn, then we can solve f(x)=0 mod m and f(x)=0 mod n. By CRT for each solution of f(x)=0 mod m and for each solution of f(x)=0 mod n we get a solution of f(x)=0 mod mn. Thus if the first congruence has r solutions and the second one has t solutions, then the congruence f(x)=0 mod mn has rt solutions.

Q :Could you provide the full procedure of finding the solutions of x^3 = 8 mod 13 ?Q：How many elements of order 6 are there modulo 13? List them all.my attempt: you look at all the elements co-prime to 13..from 1 to a12 and check which one raised to 6 gives 1mod13.

my answer:1,3,4,9,11 and 12..please verify

A:4 and 10 are the only elements of order 6 mod 13. This question is answered below.Q:How many elements of order 5 are there modulo 13?using the same method, i only got one element: 1..

A:First of all, 1 doesn't have order 5, it has order 1 (order is the LEAST power you need to raise it to to get 1.) So in this case, there are no elements of order 5 modulo 13. We proved in class that elements of order k exist only if k divides phi(n). In this case n is 13, phi(13) is 12, so you will only get elements of order 1, 2, 3, 4, 6, or 12. None of order 5.Q:How many irrational solutions x does the equation x^3 - 5x + 2 = 0 have? Find them explicitly.A:First try to find rational solutions, which is 2. Use the thm we learned on Jan. 12th," If x=m/n, (m, n coprime) is a root of a polynomial a0x^k+a1x^(k-1)+...+ak=0, then m|ak, n|a0."Then we kan get (x-2)(x^2+2x-1)=0 and solve x^2+2x-1=0. We get two irrational answers. (That is what I think, I am Kevin Chen :P) Thank you once again Kevin!

Q: Decide whether the equation x^2 - y^2 = 2 has zero, finitely many or infinitely many rational solutions x,y. Justify your answer.A:One way to solve this question would be to factor the left-hand side, to get (x+y)(x-y)=2. So write 2 as a product of two rationals a and b, with x+y=a and x-y=b.Now given any

systemof equationsx + y = a

x - y = b

we can

addor subtract the equations to get solutionsx = (a + b)/2

y = (a - b)/2

so for every possible way to write 2=ab, with rational a, b, we get rational x and y. There are infinitely many pairs a, b (let a be any nonzero rational number, and b = 2/a), so there are infinitely many solutions x, y.

(for example, 3*(2/3) = 2, so let a=3 and b=2/3. Then x = 11/6 and y = 7/6, and (11/6)^2 - (7/6)^2 = 2.

Q: Quiz2.2.2Solve the congruence

x = 3 mod 35

x = 2 mod 15

A: we can get x=35a+3 and x=15b+2, then 35a+3=15b+2 i.e 15b-35a=1. Since gcd(35, 15)=5, not 1, so there is no sol'n for "a" and "b". Hence, no such x.

(That is what I think, I am Kevin Chen :P) Thank you very much, Kevin! (Yuri)

Q:Show that if

is prime, then

Hint: order of an element modulo a prime p divides p-1

A: Order of the number 2 modulo 2^n-1 is obviously n. Thus n divides (2^n-1)-1 if 2^n-1 is prime.

Longer answer: Math @ Stack Exchange

Q:Give a characterization of primes p for which the congruence

has at least one solution.

A: This was answered below.

Q:How many elements of order 6 are there modulo 13? List them all.

I got the answer to be 3 elements: 4,10,12 but by checking all numbers. Is there any other way which is less tedious?

A:First of all, 12 is not order 6, it's order 2. So there are only two elements: 4 and 10.Once you've found one element, you can find the others pretty easily. So let's say you've checked and found that 4 is order 6. This means 4^6 = 1 mod 13. Then all other elements of order 6 will be some power of 4 - not 4^2 (because (4^2)^3 = 4^6 = 1 mod 13, so it has order 3), not 4^3 (it has order 2), not 4^4 (has order 3), but 4^5 is fine. Basically - any number relatively prime to 6 (1 or 5) will give you an exponent that will give you another remainder mod 13 of order 6.

Say, for another example, you want to find elements of order 10 modulo 31. You find 15 works. Then 15^1, 15^3, 15^7, and 15^9 will give you all elements of order 10 mod 31.

Q:How many polynomials

of degree k with coefficients 0 and 1 don't have exactly two roots?

Can such a polynomial have more than two roots?

A: The polynomial can't have more than two roots (there are only two residues, 0 and 1, modulo 2).

As for the number of polynomials f with exactly two roots, the condition is f(0)=0 and f(1)=0. This translates to conditions a_k=0, 1+a_1+...+a_k=0, giving a total of 2^{k-2} polynomials.

Q:Professor, for the midterm, should we expect questions similar to the format which we've been exposed to on our quizzes (suggested problems, etc.), or should we prepare ourselves for proofs, and questions of this nature? Thanks for your time!A: There are three questions that start with "show ..." But these are questions of the same format that appeared in suggested problems (e.g. "show that if p>3 is a divisor of n^2+n+1 then p-1 is divisible by 3").Q:Could youpleasepost the solutions to the quizzes? I know some of the answers are below, but there are a few missing. Thanks!A: No, sorry. If you are not certain about one of the quesions, please ask here.

Q:For the midterm, it states that material up to primitive element theorem and its applications will be tested. However, does that mean material up to and including the primitive element theorem and its applications, or does that mean only up to?A: The test includes questions on primitive element theorem, order of an element and applications of primitive element theoremQ: Give a characterization of primes p for which the congruence x^4 + 1 = 0 mod p has at least one solution.A: If x^4=-1 mod p then x^8=1 mod p, so order of x is a divisor of 8, i.e. it is 1, 2, 4 or 8. But x or x^2 or x^4 =1 mod p contradicts x^4=-1 mod p, so order of x is 8. Thus 8|p-1.

Conversely, if 8|p-1, then let y be a primitive root mod p and let x=y^{(p-1)/8}. Then z=x^4=y^{(p-1)/2}= -1 mod p (because z^2=1 mod p, but z is not 1).

Thus the characterization is "those primes p for which p-1 is divisible by 8".

Q: Solve the congruence x^3 = 8 mod 13^3

A: x^3=8 mod 13 has 3 solutions: x=2, x=6, x=5 mod 13.

Consider first the case of x=2 mod 13.

Let x= 2 + 13 y. Then

So we want to solve

or equivalently

This means that y=0 mod 13, i.e. y=13z. This translates to

so z=0 mod 13.

Thus we get a solution x=2 mod 13^3.

Consider now the case x=6 mod 13. Let x=6+13 y. Then we want to solve

(the term with 13^3y^3 is not included, because it is zero modulo 13^3)

or equivalently

or

Since 16+3*36y=0 mod 13, this means 3-9y=0 mod 13 or y=-4 mod 13. Let y=-4+13z and get

or equivalently

or

so z=1 mod 13.

Finally x=6+13*(-4+13(1)) mod 13^3, i.e. x=123 mod 13^3

The case x=5 mod 13 can be considered in a similar fashion.

Q:(repost) Show that every prime divisor p>3 of n^2 + n + 1 is congruent to 1 modulo 6A: Let's compute the order of n modulo p.

If n=1, then n^2+n+1=3 and p=1 or 3, contradicting p>3.

So n is not 1.

If n^2=1 mod p, then p divides n^2-1=(n-1)(n+1). Hence n=1 or -1 mod p, and hence n^2+n+1=3 or 1 mod p, contradicting that n^n+n+1=0 mod p.

Finally n^3=n(n^2)=n(-1-n)=-n-n^2=1 mod p (we are using here that 1+n+n^2=0 mod p). Thus order of n mod p is 3 and hence 3 divides p-1.

Since p is also odd, it means that p=1 mod 6.

Q:Find all solutions of x^42 = 4 (mod 100)A: x^ 42=4 mod 100 if and only if x^42=4 mod 4 and x^42 = 4 mod 25.

For the first congruence x^42=0 mod 4 the solutions are x=0 or 2 mod 4, i.e. x=0 mod 2.

For the second congruence

noticethat x must be relatively prime to 25, so x^20=1 mod 25 by Euler's theorem. Thus the equation x^42=4 mod 25 is equivalent to x^2=4 mod 25, i.e. 25|x^2-4=(x-2)(x+2). Since (x-2) and (x+2) can't be simultaneously divisible by 5, this means that 25|x-2 or 25|x+2. Thus x=2 or -2 mod 25.Finally combine this with x=0 mod 2 to get the

answerx=2 or -2 mod 50 (equivalently x=2, -2, 48, 52 mod 100)Q:For this problem: x^3 = 8 (mod13^3). I started by trying to solve x^3 = 8 (mod 13) and got x = 2,5,6 (mod13).From here, I used the method shown in class for each of x = 2,5,6 to arrive at 3 solutions for x^3 = 8 (mod13^3).

Namely, x = 2, -125, 123 (mod 13^3).

Is this the only method of doing the question, or are there any less "tedious" ways?

A: This is the right method. Unfortunately I am not aware of a less tedious method.

Q:Show that every prime divisor p>3 of n^2 + n + 1 is congruent to 1 modulo 6A: Hint: To show that p-1 is divisible by 3, show that the

orderof n modulo p is 3. Let me know if you need a more complete answer by reposting this question on the top.Q:How many polynomials

of degree k with coefficients 0 and 1 don't have any roots modulo 2?

A: The condition is that f(0)=1, f(1)=1 mod 2. The first condition is equivalent to a_k=0 mod 2. The second condition is equivalent to a_1+a_2+...+a_k=0 mod 2. Thus we can choose a_1,...,a_{k-2} in an arbitrary manner and a_{k-1} mod 2 is determined, while a_k=0 mod 2. Thus there are 2^{k-2} such polynomials.Q: How many solutions does the congruence 1+x+...+x^23 = 0 (mod111) have?A: Since 111=3x37, the congruence 1+x+...+x^23=0 mod 111 is equivalent to the system of two congruences 1+x+...+x^23=0 mod 3 and1+x+...+x^23=0 mod 37.

The first of these has 2 solutions x=1 or -1 mod 3 (just try 0, 1 and -1).

For the second equation, notice that 1+x+...+x^23=0 mod 37 is equivalent to (1-x)(1+x+...+x^23)=1-x^24=0 mod 37 and x is not congruent to 1 mod 37. The number of solutions of x^24=1 mod 37 is gcd(24,36)=12. Since x=1 is one of the solutions and we want to exclude it, we get 11 solutions of 1+x+...+x^23=0 mod 37.

By CRT we get 2x11=22 solutions for the original congruence modulo 111.

Q:find all solutions to x^7 is congruent to 15 mod 137

A: 136=8*17, so 7 is invertible modulo 136. Find the inverse s and the answer is 15^s mod 137.(s=39, 15^39=121 mod 137)

Q:find all solutions to x^17 is congruent to 0 mod 137

A: 137 is prime, so 137|x^17 if and only if 137|x.Q:if 2^n-1 is prime prove n divides 2^n-2

A: For k<n, 2^k<2^n-1.Since

this shows that order of 2 mod 2^n-1 is exactly n. Thus n divides (2^n-1)-1=2^n-2.

Q:Show that 4 is not a primitive root modulo any prime p.

A: If p is odd, then since 4=2^2,and thus the order of 4 is smaller than p-1.

If p=2, then 4=0 mod 2 and hence is clearly not a primitive root.

Q: How many solutions does x^51 = 1 (mod 137) have.Note: I solved that x^17 = 1 (mod 137) has 17 solutions. Hence

x^51 = 1 (mod 137) must have at least 17 solutions as well. I am trying to use the fact that there is no x with order 51 to prove that every x st

x^51 = 1 (mod 137) must also satisfy x^17 = 1 (mod 137), hence if this holds then that means it will also have 17 solutions.

Is this the correct approach? Please provide some clues, thank you!

A:You could do it that way indeed: if x^51=1 mod 137, the order of x mush divide both 51 and 136, hence it must be 1 or 17. In any case x^17=1 mod 137. Conversely if x^17=1 mod 137, then x^51=1 mod 137.

An

alternativeway: if x^51=1 mod 137, then x^17=1^s=1 mod 137 where s is the inverse of 3 mod 137.Yet another

solution:so first you notice that the congruence

has 17 solutions and then for each solution y the congruence

has only one solution

(because 3x91 = 1 mod 136)

Q: In class we covered the problem x^2 + ax+ b = 0 (mod p). Could you re-explain this example with emphasis on(i) Why you divided the cases into p=2 and p does not equal 2

(ii) The case when p=2, it suffices to solve x^2 = 0, x^2 + x =0, x^2+1 =0, x^2+x+1=0.

A: (i) The trick with completing the square, or, equivalently, the formulaworks only if we can divide by 2. If p is equal to 2, we can't do it, so we have to consider p=2 separately.

(ii) If p=2, the coefficients a, b could only be 0 or 1 mod p. Thus there are only 4 equations to solve and each one of them is easily solvable.

Q: Could you please provide a list of which chapters from the textbook we have covered? Thanks！A: We covered 1,2,3,5,6,8,9,10,11,12,16,17,18,19,20,21,22,part of 23,part of 24Q: From the question that was solved belowThe solution was x = 3. Why do we not include x = 3 * (k * 7 + 1), k>=1 as other solutions to the congruence?

A: The answer iswhich is equivalent to saying x=3+21 k for any integer k.

Q：How many solutions does the congruence x^40= 1 (mod100) have?

A: Since x^40=100m+1, it means that gcd(x,100)=1 (because 1 is divisible by gcd(x,100)).If x is relatively prime to 100, then x^{\phi(100)}=1 (mod 100). \phi (100)= (4-2)(25-5)=40.

So x is the solution of x^40=1(mod 100) if and only if x is relatively prime to 100.

There exactly \phi(100)=40 distinct (modulo 100) numbers that are relatively prime to 100.

Answer:The congruence has 40 solutionsQ:N=pq, where p and q are distinct primes.there exist x and y, such that x*2=y*2 mod N, but x is not congruent to y mod N, and x is not congruent to -y mod N. find p and q.

A: It's impossible to determine p and q: one can have x=y mod p and x=-y mod q for any distinct p and q.Q:How many solutions does the congruence x^40 is congruent to 2 mod100 haveA: This congruence doesn't have a solution. If x^40=2 mod 100, then x is even, but then x^40 is divisible by 4 so can't be equal to 2 mod 100.Q:I was wondering if you could provide the answers for 18.2 please.18.2 (a) Show that in fact RSA decryption does work for all messages a, regardless of whether or not they have a common factor with m.

(b) More generally, show that RSA decryption works for all messages a as long as m is a product of distinct primes.

(c) Give an example with m=18 and a=3 where RSA decryption does not work (remember, k must be chosen relatively prime to phi(m)=6).

Parts (a) and (b) are similar to 17.4 which asks to show that b^u as found by Algorithm 17.1 is still a solution for "x^k is congruent to b mod m" if gcd(b,m)>1 but m is a product of distinct primes. u is a solution to ku-phi(m)v=1.

A: a,b) Let N=p_1p_2 ... p_n for distinct primes p_iRSA algorithm starts with message a and outputs a^{ks} mod N where ks = 1 mod phi(N).

The message a could be divisible by p_i or not divisible by p_i. If it is, then a^{ks}=0=a mod p_i. If a is relatively prime to p_i, then a^phi(N)=1 mod p_i, since phi(N) is divisible by p_i - 1. In particular a^{ks}=a mod p_i. Thus regardless of what a is, a^{ks}=a mod p_i for all i and hence a^{ks}=a mod N by CRT.

Q:Feb 07:Solve the congruence x^2+x-1=0 mod 11A: 11 is a prime number, so we can divide. x^2+x-1=(x+1/2)^2-5/4=0 (mod 11). 1/4=3 (mod 11), so (x+1/2)^2=4 (mod 11), so x+1/2=2 (mod 11) or x+1/2=-2 (mod 11). 1/2=6 (mod 11), so x=3 (mod 11) or x=7 (mod 11)Q:general question about fermat: does p have to be necessarily prime?consider: 7^5=1 mod6, 6 is not prime, only that 7 and 6 are co-prime. please advise, thx.

A: Fermat's little theorem guarantees thatifp is prime, then a^(p-1)=1 mod p for all a not divisible by p. It doesn't say anything about whether for a composite number n the equality a^(n-1)=1 mod n holds for some particular values of a. In your example 7^5=1^5=1 mod 6, but the reason has nothing to do with FLT (it has to do with the fact that 1 raised to any power is still 1).Q: 9.4 a) from jan 26:is true, prove m=1734251

is composite.

it cannot be sufficient to simply state that since 7*1734250 is not congruent to 1 modm, m is not prime?

A: If m is prime, then by FLTSince this equality doesn't hold, m is not prime.

Q:Find a multiple of 77 that ends with 999attempted:

77x=999mod1000 (subtracting 999 from that multiple would leave 3 0s)

but

cameup with x=12987; clearly wrong, please correct!A: 12987*77=999999Q:find the non-negative solutions of 7x+19y=1A: if x>0 or y>0 then 7x+19y>1. If x=0 and y=0, then 7x+19y=0. Thus there are no non-negative solutions of this equation.

Q:Show that the congruence

x^2 = a (mod21)

can have 0, 1, 2 or 4 solutions depending on a

I tried to show this by using CRT: since 21 is the product of 3 and 7, I worked with two congruences

(1): x^2=a(mod3) and

(2): x^2=a(mod7)

then showed that both congruences can have 0, 1 or 2 solutions (depending on a) (by solving for a= 0, 1, 2 for (1) and a = 0, 1, 2, ..., 6 for (2)), which

implied that (3): x^2=a(mod 3*7=21) has 0, 1, 2, or 4 solutions (depending on a) (since multiplying the number of solutions for (1) and (2) with the same value of a gives the number of solutions for (3)).

Is this correct or are there any less tedious methods?

A: This is correct.We have recently learned a theorem that equation of degree n has at most n different roots modulo a prime p, which shows immediately that x^2=a mod 3 and x^2=a mod 7 each have 0,1 or 2 solutions, but without using it what you did is indeed the best way.

Q1Find 2^220 (mod 221) Conclude that 221 is composite.A: Use successive squaring:

2^220=4^110=16^55=16*256^27=16*35^27=16*35*1225^13=16*35*120^13=16*35*120*14400^6=16*35*120*35^6=16*35*120*120^3=16*35*120*120*35=16 mod 221

If 221 were prime, then 2^220 would have been 1 mod 221 by FLT. Hence 221 is composite.

Q2Show that a^48=1 (mod 221) for all a relatively prime to 221.A: 221=13*17

a^48=a^(12*4)=1 mod 13 by FLT

a^48=a^(16*3)=1 mod 17 by FLT

Thus a^48=1 mod 221 by CRT

Q:Solve the congruence

(*)

A: if x is the solution of (*) we have x^7=3(mod 7), x^7=0(mod 3) so 3|x.

y^6=1(mod 7) for all y that are coprime with 7. So (since our x is clearly coprime with 7)

x^7=x^6*x=x=3(mod 7). So x=0(mod 3) x=3 (mod 7) but chinese remainder theorem

the solution mod 21 is unique and 3 is clearly the solution.

Q: According to Feb 2 lecture, X^24 = 1 (mod 35) has phi(35) = 24 solutions. Why is this?

A: By the Euler theorem any x such that (x,m)=1 satisfies

So for m=35 phi(35)=(5-1)(7-1)=24 so any x that is coprime (and there exactly 24 such x mod 35) with 35 is a solution of x^24=1 (mod 35)

if x is not coprime with 35 then it can't be the solution because (1,35)=1.

Q:

A: 6= (-1) (mod 7),

6x=(-x) (mod 7),

6x=-x=5(mod 7)

x=-5 (mod 7)

x=2 (mod 7)

Q: 11.1 b) Determine the value of

A:

Q: 11.5 Find x that solves

and

A: We should solve

x=3+37k, x=1+87m, or, equivalently, 3+37k=1+87m, i.e. 87 m - 37 k = 2.

Rewrite this as 13m - 37 (k - 2m) = 2 and let k'=k-2m. Rewrite 13m - 37 k' = 2 as 13(m-3k') + 2 k' = 2. One solution is m-3k'=2, k' = - 12. Thus m= -34, k=k'+2m = -80.

Thus x=3+37 k = 3 - 37*80= - 2957.

(This is only one possible solution. Other ones are given by -2957 + 87*37 t with integer t).

Q: Show that for

the congruence

holds for every a relatively prime to m.

(Hint: use Fermat's little theorem to compute a^{m-1} mod p for every prime divisor p of m).

A: This was shown in class Tuesday, January 31.

Q:Find the remainder when a is divided by m (a) a=207^321+689! m=7(b) a=(123)(45)(678)(910)(112) m=6

A: a) 689! is divisible by 7.207=(-3) mod 7 and (-3)^6= 1 mod 7 by FLT. Thus 207^321 = (-3)^(53*6+3)= (-3)^3 = 1 mod 7.

b) 678 is divisible by 6, so the whole product is also divisible by 3.

Q:For the following two questions:9.4 a) Assuming that the congruence

holds, show that 1734251 is a composite (i.e. non-prime) number.

c) The congruence

is true. Can you conclude that 52633 is a prime number?

Is it enough to just show by using Fermat's little theorem?

A: In a) FLT shows that 1734251 is composite.In c) FLT doesn't show anything.

Q:8.4 (d) Show that a number is divisible by 9 if and only if its sum of digits is divisible by 9.A: Let the number bei.e. the digits are a_0,a_1,...,a_n.

Then

This shows that the remainder of division of the number by 9 is the same as the remainder of division of its sum of digits by 9.

Q:based on 2.1 (b) Show that in a primitive Pythagorean triple a,b,c exactly one of a,b,c is divisible by 5.A: Modulo 5 all the squares are congruent to 0 or plus/minus 1. If a^2+b^2=c^2 mod 5 and (a,b,c) is not (0,0,0) mod 5, the only options areIn each of these cases exactly one of a,b,c is equal to 0 mod 5.

Q:Find all integer solutions of the equation 65432 x + 98765 y = gcd(65432,98765)A: 98765=65432+33333, so we rewrite this equation as 65432 x' + 33333 y = gcd (65432, 33333) with x'=x+y.Next 65432 = 2*33333-1234, so we rewrite the equation as -1234 x' + 33333 y' = gcd ( -1234, 33333) where y' = y+2x'.

Next 33333 = (-27)*(-1234) + 15, so we rewrite the equation as -1234 x'' + 15 y' = gcd ( -1234, 15) where x''=x'-27y'

Next -1234 = (-82)(-15)-4, so we rewrite the equation as -4 x'' + 15 y'' = gcd(-4,15) where y''=y'-82x''

Finally 15 = (-4)(-4)-1, so we rewrite the equation as -4x''' - y'' = gcd(-4,-1)=1, with x'''=x''-4y''.

One solution of this equation is x'''=0, y''=-1, i.e. x''=-4, y'=y''+82x''=-329, x'=x''+27y'=-4+27*(-329)=-8887, y=y'-2x'=-329+2*8887=17445, x=x'-y=-8887-17445=-26332.

All other solutions are given by x=-26332 + 98765 k, y=17445 - 65432 k, k - any integer.

Q: Find 10^5^101 (mod 21)A: 10=1 mod 3, so 10^5^101 is 1 mod 3.By FLT, 10^6=1 mod 7. Now we want to divide the exponent 5^101 by 6 with remainder. We see immediately that 5^101=(-1)^101= -1=5 mod 6. Thus 10^(5^101)=10^(6q+5)=10^5 mod 7.

Finally 10^5=3^5=5 mod 7.

Combining these two

resultsusing CRT we find that 10^5^101=19 mod 21.Q: Find a numberwith

A: 73 is a prime number, so by FLT 9^72 = 1 mod 73. Now 794=11*72+2, so 9^794=9^2=81=8 mod 73Q.Show that for a prime number p the number (p-1)!+1 is divisible by p(Hint: consider the number (p-1)! mod p. In this product one can split most of the residues to pairs of a residue and its inverse).

A: In the product

every residue comes with its inverse modulo p. In general these two residues x and x^{-1} are different from each other, except when x=x^{-1}, or, equivalently, x^2=1, i.e x=1 or -1.

Thus (p-1)!= -1 mod p.

Q.Does

x^10+y^10 = 11z^10

have non-zero solutions mod 6?

could it be shown using mod 6 instead of 4 from the answer below?

A: For a non-zero x, x^2=1,4,3 mod 6, so x^10=1,4,3 mod 6. Same holds for y^10. 11z^10 is 5,2,3 mod 6.So 1^10+4^10=11*1^10 mod 6 is a non-zero solution mod 6.

So I don't see an obvious way of concluding non-existence of non-zero solution by trying to do it mod 6 instead of mod 4.

Q.Determine the value of 2^2012+3^3013(mod7)A:Compute first 2^2012 mod 7.

2^3=1 mod 7, so 2^2010=1^670=1 mod 7 and so 2^2012=4 mod 7.

Now 3^6=1 mod 7. Apply this to compute 3^3013 mod 7 in the same way: 3^3013=3^3012 * 3 =3 mod 7.

Thus 2^2012+3^3012 = 0 mod 7

Q:2.6) b) Find a Pythagorean triple (a,b,c) with c=a+2 and c>1000.c) Find all primitive Pythagorean triples (a,b,c) with c=a+2.

A: a^2+b^2=(a+2)^2 means 4a+4=b^2. This equation has a solution for every even number b: b=2k, a=k^2-1. If k is odd, a is even and the triple (a,b,a+2) is not primitive. However if k is even, then gcd(k^2-1,k)=gcd(-1,k)=1, so gcd(k^2-1,2k)=1 and thus the triple is primitive.

In short all the primitive solutions are of the

form(k^2-1,2k,k^2+1) with even k.Q: SolveA:So the solutions are 3 and -3 mod 7.

Q: Show that there are infinitely many primes of the for 6n+5.A: First notice that every prime number, except 2 and 3 is congruent to either 1 or -1 mod 6.Consider the number 6n!-1. All its divisors are at least n and among its prime divisor at least one must be congruent to -1 mod 6 (because the product is congruent to -1 mod 6).

Q:Show that the equationhas no non-zero integer solutions.

A:We can assume gcd(x,y,z)=1

Let's

lookat the remainder of the both sides modulo 4.so x^{10}+y^{10} mod 4 can be 0 (if they are both even), 1 or 2

11z^{10} mod 4 can be 0 (if z is even) or 3.

But

x^{10}+y^{10}=11z^{10}, so both sides are 0 mod 4 and x,y,z are all even,

that condradicts with the assumption gcd(x,y,z)=1.

Q: (2.3) Which odd numbers a can appear in a primitive Pythagorean triple (a,b,c)?

A:Any odd a can appearQ:Which even numbers b can appear in a primitive Pythagorean triple (a,b,c)?A:If b is not divisible by 4 it cannot appear in the Pythagorean triple.

Let's look at the remainders of both sides modulo 8.

a, c are odd so their squares can be only 1 mod 8. If b is not divisible by 4

b^2 mod 8 is 4, so a^2+b^2 mod 8=5 that is not equal to one.

If b is divisible by 4 take b=2^{k}d, where d is odd. We know that k>1.

Then take the Pythagorean triple a=2^{2k-2} - d^{2}, b, c=2^{2k-2} + d^{2}.

Since k>1 a is odd.

gcd(a,b,c)=1 (assume the contrary, there exist prime p that divides a,b,c. Since a is odd p is odd. Odd prime p divides b, so it must divide d, so p must divide a+d^{2} that is a power of two. contradiction).

So we constructed a primitive Pythagorean triple with the given b.

Q: (2.1)We showed that in any primitive Pythagorean triple (a,b,c) either a or b is even. Use the same sort of argument to show that either a or b must be a multiple of 3.A: Consider the identity a^2+b^2=c^2 mod 3. If neither a nor b are divisible by 3, then

and similarly for b^2. Thus a^2+b^2 = 2 mod 3, which is not a square of anything mod 3.

Thus either a or b must be divisible by 3.

Q: Show that the equation x^2 + x = y^2 has no non-zero integer solutionsA:Since x, (x+1) can't have common divisors if some prime p divides x, then p^2 divides x (since p divides y, so p^2 divides x(x+1) and gcd(x+1,x)=1). So

for some integer a. For the same reason

for some integer b. But it means that we got two plus/minus squares of integers with the difference one, so x=0 or x=-1.

Q: Show that if x, y,z have no common factors and satisfy the equation above (x^2 + 2y^2=z^2)Then one can find integers s,t such that either z-x=2s^2, z+s=t^2 or z-x=s^2, z+x=2t^2.

A:First of all notice that x,z must be odd (if x is even, z is also even and it follows easily that y must be even as well).Now rewrite the equation as 2y^2=x^2-z^2=(x-z)(x+z).

Notice that gcd(x-z,x+z)=gcd(x-z, 2x)=2gcd(x,z)=2.

Thus the only common factor of (x-z) and (x+z) is 2.

It follows that all the exponents of the primes other than 2 in the factorizations of x-z and x+z are even. The exponent of 2 is even in one of them and odd in the other one.

Thus either x-z=2s^2, x+z=t^2 or x+z=2s^2, x+z=t^2.

The required parametrization follows.

Q: Solve the equation x^2 + 2y^2=z^2 in integers.A: See question above.

Q: (2.4)In our list of examples are the two primitive Pythagorean triples

Find at least one more example of two primitive Pythagorean triples with the same value of c. Can you find three primitive Pythagorean triples with the same c? Can you find more than three?

A: I am sorry for assigning this question: it seems a bit tougher than I expected it to be.

One possible approach to it is to use the following identity:

(we will later learn how this identity naturally appears from some basic properties of complex numbers).

This identity allows you to get a representation of some numbers as sum of two squares in two different ways.

To get a representation of a number as a sum squares in four different ways, use this identity twice:

and now use the identity once again.

Q: Show thatfor any natural numbers m,n.

A:We showed in class that ifthen

Let's now divide n by m with remainder: n= qm+r. By applying the result above q times, we get that

So if we want to compute gcd(10^x-1,gcd^y-1), we can always replace the pair of parameters (x,y)=(n,m) by the pair (x,y)=(m,r) without changing the answer.

We know from what we have discussed about Euclid's algorithm that we can repeat this procedure until we get to the pair (gcd(m,n),0). For this pair the value of gcd(10^x-1,10^y-1) is

Q:Find an integer solution ofwith a>1000 and with a, b, c having no common factor.

A:Let x=a/c, y=b/c. Then we want to find a rational solution x,y to the equation x^2+xy+y^2=3. One solution is x=1, y=1.We showed in class that all rational solutions of such equation are given by intersecting the quadric with lines of the kind y-1 = m(x-1) with rational m. Plugging the value of y from the equation of the line into the equation of the quadric we find

x^2+x(mx+1-m)+(mx+1-m)^2=3, or, equivalently, (1+m+m^2)x^2+(1-m+2m(1-m))x+(1-m)^2-3=0.

One solution of this equation is x=1, so the second solution is

and

It remains to choose a large enough m so that the numerator and denominator in the fractions will be large enough, e.g. m=50 that gives a=2398, b= - 5099, c= 2551 (check that these are relatively prime!) .

Q: January 10 question1Prove that

has no nonzero solutions

A: We can assume that gcd(m,n)=1, otherwise writethen

Now m_1 is divisible by three, so

is divisible by 9, so n_1 is divisible by three. We get the contradictionh with the fact that

Q: January 10 question4Prove that if

and x,y,z have no common factors, then x and z must be odd and y must be even.

A: Assume x is even, thenis also even, so z is even and

is divisible by 4, so y is even and x,y,z have the common factor 2.

So x is odd and so is z (as a sum of odd and even number). Now if x,z are both odd then

is divisible by 4 and so y is even.

Q: January 10 question3prove

has no solutions with x and y both odd

A: If x is odd, z must be odd as well. Let x=2k+1, y=2n+1, z=2m+1 the equation translates into 4k^2+4k+8n^2+8n+3=4m^2+4m+1. The left side gives remainder of 3 when divided by 4, while the right side gives remainder of 1. Thus no solution with odd x, y could possibly exist.Q:Show that

is irrational. (Hint:

A:Applying the hint we find that

satisfies the equation

or, equivalently, 8x^3-6x-1=0. By a theorem we proved in class the only candidates for rational solutions of this equation are

By

checkingeach one of these we find that the equation has no rational solutions, so x must be irrational.Q: Find at least one integer solution to the equation 21x - 13 y = 1A: Write the equation as 8 x + 13 (x-y) =1, let y'=x-y.Now solve 8x + 13 y' = 1

Write it as 8 (x+y')+5 y' = 1

Let x'=x+y'

Solve 8x'+5y'=1

Write it as 3x'+5(x'+y')=1

Let y''=x'+y'

Solve 3x'+5y''=1

Write it as 3(x'+y'')+2y''=1

Let x''=x'+y''

Solve 3x''+2y''=1, or x''+2(x''+y'')=1.

One solution: x''=1, x''+y''=0, i.e. x''=1, y''=-1.

Now unwind the substitutions: x'=x''-y''=2

y'=y''-x'=-3

x=x'-y'=5

y=x-y'=8.

Thus one solution is x=5, y=8 (check: 21*5-13*8=105-104=1).

All other solutions are of the

formx=5+13k, y=8+21k.Q: Please provide some hints on how to do the second problem for January 10th:Show that the equation x^2+x=y^2 has no non-zero integer solutions

Hint: If you want to show that something (x^2+x) is not a square of an integer, try to prove that itcan't fit into the "gap" between two consecuitive squares.

A hint to a different solution: rewrite the equation in the formand use that x, x+1 are relatively prime.

Q: Show that ifis a rational number, then it is an integer.

A: If n=a^2/b^2 for some integers a, b, then nb^2=a^2. Let p be any prime number and let k_a, k_b, k_n denote the multiplicities of this prime in the prime factorizations of a, b, n respectively. The equality nb^2=a^2 and uniqueness of factorization to primes tells us then that k_n + 2 k_b = 2 k_a. Thus k_n is even.Hence the prime number factorization of n is of the form

and hence square root of n is integer.

Introduction to Number Theory

Introduction to Number Theory

(\pm 1)^2,(\pm 2)^2,

(\pm 3)^2,(\pm 4)^A,