# 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 17 8 19 17 3 4 2 1 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
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 side contradiction 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 + 4 then 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 divides x^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 q by 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: 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
 x^2-9y^2=1

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

NQ: (not a question, but) Proof that -1 is a norm in
$\mathbb{Z}_p[i], p\equiv 3 \mod 4;$
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
$a^2+1\equiv -c^2\mod p$
and so
$(\frac{a}{c})^2+(\frac{1}{c})^2\equiv -1\mod p$
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
$\gcd(y-i,y+i)=\gcd(2i,y+i)=\gcd((1+i)^2,y+i)$
Let's check whether y+i is divisible by 1+i:
$\frac{(y+i)}{1+i}=\frac{(y+i)(1-i)}{2}=\frac{y+1}{2}+\frac{1-y}{2}i$
Since y is even, this shows that y+i is not divisible by 1+i. Thus y-i, y+i are coprime.

Hence
$y-i=u s^3, y+i = v t^3$
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
$s^3=a^3-3ab^2+i(3a^2b-b^3)$
Then
$y-i=u(a^3-3ab^2+i(3a^2b-b^3))$
In particular comparing the imaginary parts we find that
$a^3-3ab^2=\pm 1 \mbox{ or } 3a^2b-b^3=\pm 1$
i.e.
$a(a^2-3b^2)=\pm 1 \mbox{ or } b(3a^2-b^2)=\pm 1$
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
$x^2+y^2\equiv (x+ay)(x-ay) \mod p$

Make an invertible change of variables:
$z=x+ay, w=x-ay$
(the inverse transformation is given by
$x=(z+w)/2, y=(z-w)/(2a)$
)
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
$y\equiv\frac{y_0}{x_0-1}(x-1), x^2+y^2\equiv 1 \mod p$
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
$m^2+1\not\equiv 0 \mod p$
then the system
$y\equiv m(x-1), x^2+y^2\equiv 1 \mod p$
has two solutions: (1,0) and
$(\frac{m^2-1}{m^2+1},\frac{-2m}{m^2+1})$
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 complete answer 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:

$7!=2\cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 = 2^4\cdot 3^2 \cdot 5 \cdot 7$
Now factor these primes as products of Gaussian primes:

$7!=(1+i)^8\cdot 3\cdot 7\cdot (2+i)\cdot (2-i)$
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
$z\cdot \bar{z}=N(z)=p^2$
and p is congruent to 3 mod 4, then the factorization of
$z\cdot \bar{z}$
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
$N(z)=z\cdot \bar{z}$
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
$\left(\frac{-7}{p}\right)=(-1)^{(p-1)/2}(-1)^{\frac{7-1}{2}\cdot\frac{p-1}{2}} \left(\frac{p}{7}\right)= \left(\frac{p}{7}\right)$
Thus it is 1 if and only if p is congruent to 1, 2 or 4 modulo 7.

Q:
Compute
$\left(\frac{-32}{101}\right)$
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：
$\left(\frac{14}{101}\right)$
A:
$\left(\frac{14}{101}\right)= \left(\frac{2}{101}\right) \left(\frac{7}{101}\right)$
Now (2/101)=-1 because 101=-3 mod 8
$\left(\frac{7}{101}\right)= \left(\frac{101}{7}\right)= \left(\frac{3}{7}\right)=-1$
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
$x_k+\sqrt{5}y_k=(4+\sqrt{5})(9+4\sqrt{5})^k$
(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
$x_k + y_k \sqrt{5} = (9+4\sqrt{5})^k$
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,
$\left(\frac{5}{p}\right)= \left(\frac{p}{5}\right)$
The quadratic residues modulo 5 are 1 and -1. Hence the answer is
$p\equiv \pm 1 \mod 5$
Q: What are all the quadratic residues modulo 19.

A:
$(\pm 1)^2,(\pm 2)^2, (\pm 3)^2,(\pm 4)^2, (\pm 5)^2,(\pm 6)^2, (\pm 7)^2,(\pm 8)^2,(\pm 9)^2\equiv 1,4,9,16,25,36,49,64,81\equiv 1,4,9,-3,6,-2,-8,7,5 \mod 19$
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
$(x^2+1)(x^2+2)(x^2-2)\equiv 0 \mod p$ 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.
$\left(\frac{p-a}{p}\right)= \left(\frac{-a}{p}\right)= \left(\frac{-1}{p}\right) \left(\frac{a}{p}\right)= (-1)^{\frac{p-1}{2}}$

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:
$\left( \frac{3}{p} \right)=(-1)^{\frac{3-1}{2}\cdot\frac{p-1}{2}}\left( \frac{p}{3} \right ) = (-1)^{2^{k-1}} \left( \frac{(-1)^k+1}{3} \right)$
If k>1 and k is even, then this number is equal to
$\left( \frac{2}{3} \right) = -1$
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:
$x^2+x-1=(x+2^{-1})^2-1-(2^{-1})^2=(x+6)^2-1-6^2=(x+6)^2-4=0 \mod 11$

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.

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
$x^3\equiv 8+3\cdot 4 \cdot 13y +3 \cdot 2\cdot (13)^2 y^2 \mod 13^3$
So we want to solve
$3\cdot 4 \cdot 13y +3 \cdot 2\cdot (13)^2 y^2 \equiv 0 \mod 13^3$
or equivalently
$12 y +6\cdot 13 y^2 \equiv 0 \mod 13^2$
This means that y=0 mod 13, i.e. y=13z. This translates to
$12 z \equiv 0 \mod 13$
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

$(6+13y)^3-8\equiv 6^3-8+3\cdot 6^2 \cdot 13y +3 \cdot 6\cdot (13)^2 y^2 \equiv 0 \mod 13^3$
(the term with 13^3y^3 is not included, because it is zero modulo 13^3)

or equivalently

$13\cdot 16+3\cdot 6^2 \cdot 13 y +3 \cdot 6\cdot 13^2 y^2 \equiv 0 \mod 13^3$
or
$16+3\cdot 6^2 y +3 \cdot 6\cdot 13 y^2 \equiv 0 \mod 13^2$

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
$16+3\cdot 6^2 (-4+13z) +3 \cdot 6\cdot 13 (-4+13z)^2 \equiv 0 \mod 13^2$
or equivalently
$256+3*6^2z \equiv 0 \mod 13$
or
$9+4z \equiv 0 \mod 13$
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
$f(x)=x^k+a_1x^{k-1}+\ldots+a_k$
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
$2^n\equiv 1 \mod 2^n-1$
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,
$4^{\frac{{p-1}{2}}=2^{p-1}\equiv 1 \mod p$
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.

Yet another solution:
$x^{51}=(x^3)^{17}$
so first you notice that the congruence
$y^{17}\equiv 1 \mod 137$
has 17 solutions and then for each solution y the congruence
$x^3\equiv y \mod 137$
has only one solution
$x\equiv y^{91}\mod 137$
(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
$x=\frac{-a\pm\sqrt{a^2-4b}}{2}$
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
$x^7\equiv 3 \mod 21$
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
$x\equiv 3 \mod 21$
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).

Q: 9.4 a) from jan 26:
$7^{1734250}\equiv 1660565 \mod 1734251$
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 FLT
$7^{m-1}\equiv 1 \mod m$
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
$x^{\phi(m)}=1 \mod m$
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:
$6x\equiv 5 (\mod 7)$
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
$\phi(8800)$

A:
$8800=2^{5}\times 5^{2}\times 11$
$\phi(8800)=(2^{5}-2^{4})(5^{2}-5^{1})(11^{1}-11^{0})=8800(1-\frac{1}{2})(1-\frac{1}{5})(1-\frac{1}{11})$

Q: 11.5 Find x that solves
$x\equiv 3 \mod 37$
and
$x\equiv 1 \mod 87$
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
$m=561=3\cdot 11\cdot 17$
the congruence
$a^{m-1}\equiv 1 \mod m$
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
$7^{1734250}\equiv 1660565 \mod 1734251$
holds, show that 1734251 is a composite (i.e. non-prime) number.
c) The congruence
$2^{52632}\equiv 1 \mod 52633$
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
$\overline{a_0a_1\ldots a_n}=a_n+10a_{n-1}+\ldots+10^n a_n$
i.e. the digits are a_0,a_1,...,a_n.

Then
$a_n+10a_{n-1}+\ldots+10^n a_n \equiv a_n+a_{n-1}+\ldots+a_n \mod 9$
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
$\pm 1 \mp 1 \equiv 0, 0 \pm 1\equiv \pm 1, \pm 1 + 0 \equiv \pm 1$
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
$0\leq a < 73$
with
$a\equiv 9^{794} \mod 73$
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
$1\cdot 2\cdot 3\cdot \ldots\cdot (p-1)$
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
$x^2 \equiv 2 (\mod 7)$
A:
$0^2\equiv 0, (\pm 1)^2 \equiv 1, (\pm 2)^2\equiv 4, (\pm 3)^2\equiv 2 \mod 7$
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
$x^{10}+y^{10}=11z^{10}$
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.
$x^{10}=(x^5)^2$
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
$a^2+(\frac{a^2-1}{2})^{2}=(\frac{a^2+1}{2})^{2}$
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
$a^2\equiv (\pm 1)^2\equiv 1 \mod 3$
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:
$y^2= x^2+x=x(x+1)$
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
$x=\pm a^2$
for some integer a. For the same reason
$x+1=\pm b^2$
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
$33^2 + 56^2 = 65^2 and 16^2 + 63^2 = 65^2$
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:
$(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2=(ad-bc)^2+(ac+bd)^2$
(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:
$(a^2+b^2)(c^2+d^2)(e^2+f^2)=[(ac-bd)^2+(ad+bc)^2](e^2+f^2)=[(ad-bc)^2+(ac+bd)^2](e^2+f^2)$
and now use the identity once again.

Q: Show that
$\gcd(10^n-1,10^m-1)=10^{\gcd(m,n)}-1$
for any natural numbers m,n.

A: We showed in class that if
$n\geq m$
then
$\gcd(10^n-1,10^m-1)=\gcd({10^{n-m}-1,10^m-1})$
Let's now divide n by m with remainder: n= qm+r. By applying the result above q times, we get that
$\gcd(10^n-1,10^m-1)=\gcd({10^r-1,10^m-1})$
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
$\gcd(10^{\gcd(m,n)}-1,0)=10^{\gcd(m,n)}-1$
Q:Find an integer solution of
$a^2+ab+b^2=3c^2$
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

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
$x=\frac{(1-m)^2-3}{1+m+m^2}=\frac{m^2-2m-2}{m^2+m+1}$
and
$y=m(x-1)+1=m( \frac{m^2-2m-2}{m^2+m+1}-1) +1=\frac{1-2m-2m^2}{m^2+m+1}$
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
$m^2=3n^2$
has no nonzero solutions

A: We can assume that gcd(m,n)=1, otherwise write
$m_1=\frac{m}{gcd(m,n)}, n_1=\frac{n}{gcd(m,n)}$
then
$gcd(m_1,n_1)=1, m_1^{2}=3n_1^{2}$
Now m_1 is divisible by three, so
$3n_1^{2}=m_1^{2}$
is divisible by 9, so n_1 is divisible by three. We get the contradictionh with the fact that
$gcd(m_1,n_1)=1$
Q: January 10 question4
Prove that if
$x^2+2y^2=z^2$
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
$x^2+2y^2$
is also even, so z is even and
$2y^2=x^2-z^2=(x-z)(x+z)$
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
$2y^2=x^2-z^2=(x-z)(x+z)$
is divisible by 4 and so y is even.

Q: January 10 question3
prove
$x^2 + 2y^2=z^2$
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
$\cos 20^o$
is irrational. (Hint:
$\cos 3\alpha = 4\cos^3\alpha - 3 \cos \alpha)$
A:

Applying the hint we find that
$x=\cos 20^o$
satisfies the equation
$\frac 12 = 4x^3-3x$
or, equivalently, 8x^3-6x-1=0. By a theorem we proved in class the only candidates for rational solutions of this equation are
$\pm 1, \pm \frac 12, \pm \frac 14, \pm \frac 18$
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
$x(x+1)=y^2$
and use that x, x+1 are relatively prime.

Q: Show that if
$\sqrt n$
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
$p_1^{2t_1}\cdot \ldots \cdot p_m^{2t_m}$
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
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 side contradiction 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 + 4 then 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 divides x^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 q by 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: 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
 x^2-9y^2=1

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

NQ: (not a question, but) Proof that -1 is a norm in
$\mathbb{Z}_p[i], p\equiv 3 \mod 4;$
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
$a^2+1\equiv -c^2\mod p$
and so
$(\frac{a}{c})^2+(\frac{1}{c})^2\equiv -1\mod p$
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
$\gcd(y-i,y+i)=\gcd(2i,y+i)=\gcd((1+i)^2,y+i)$
Let's check whether y+i is divisible by 1+i:
$\frac{(y+i)}{1+i}=\frac{(y+i)(1-i)}{2}=\frac{y+1}{2}+\frac{1-y}{2}i$
Since y is even, this shows that y+i is not divisible by 1+i. Thus y-i, y+i are coprime.

Hence
$y-i=u s^3, y+i = v t^3$
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
$s^3=a^3-3ab^2+i(3a^2b-b^3)$
Then
$y-i=u(a^3-3ab^2+i(3a^2b-b^3))$
In particular comparing the imaginary parts we find that
$a^3-3ab^2=\pm 1 \mbox{ or } 3a^2b-b^3=\pm 1$
i.e.
$a(a^2-3b^2)=\pm 1 \mbox{ or } b(3a^2-b^2)=\pm 1$
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
$x^2+y^2\equiv (x+ay)(x-ay) \mod p$

Make an invertible change of variables:
$z=x+ay, w=x-ay$
(the inverse transformation is given by
$x=(z+w)/2, y=(z-w)/(2a)$
)
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
$y\equiv\frac{y_0}{x_0-1}(x-1), x^2+y^2\equiv 1 \mod p$
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
$m^2+1\not\equiv 0 \mod p$
then the system
$y\equiv m(x-1), x^2+y^2\equiv 1 \mod p$
has two solutions: (1,0) and
$(\frac{m^2-1}{m^2+1},\frac{-2m}{m^2+1})$
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 complete answer 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:

$7!=2\cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 = 2^4\cdot 3^2 \cdot 5 \cdot 7$
Now factor these primes as products of Gaussian primes:

$7!=(1+i)^8\cdot 3\cdot 7\cdot (2+i)\cdot (2-i)$
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
$z\cdot \bar{z}=N(z)=p^2$
and p is congruent to 3 mod 4, then the factorization of
$z\cdot \bar{z}$
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
$N(z)=z\cdot \bar{z}$
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
$\left(\frac{-7}{p}\right)=(-1)^{(p-1)/2}(-1)^{\frac{7-1}{2}\cdot\frac{p-1}{2}} \left(\frac{p}{7}\right)= \left(\frac{p}{7}\right)$
Thus it is 1 if and only if p is congruent to 1, 2 or 4 modulo 7.

Q:
Compute
$\left(\frac{-32}{101}\right)$
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：
$\left(\frac{14}{101}\right)$
A:
$\left(\frac{14}{101}\right)= \left(\frac{2}{101}\right) \left(\frac{7}{101}\right)$
Now (2/101)=-1 because 101=-3 mod 8
$\left(\frac{7}{101}\right)= \left(\frac{101}{7}\right)= \left(\frac{3}{7}\right)=-1$
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
$x_k+\sqrt{5}y_k=(4+\sqrt{5})(9+4\sqrt{5})^k$
(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
$x_k + y_k \sqrt{5} = (9+4\sqrt{5})^k$
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,
$\left(\frac{5}{p}\right)= \left(\frac{p}{5}\right)$
The quadratic residues modulo 5 are 1 and -1. Hence the answer is
$p\equiv \pm 1 \mod 5$
Q: What are all the quadratic residues modulo 19.

A:
$(\pm 1)^2,(\pm 2)^2, (\pm 3)^2,(\pm 4)^2, (\pm 5)^2,(\pm 6)^2, (\pm 7)^2,(\pm 8)^2,(\pm 9)^2\equiv 1,4,9,16,25,36,49,64,81\equiv 1,4,9,-3,6,-2,-8,7,5 \mod 19$
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
$(x^2+1)(x^2+2)(x^2-2)\equiv 0 \mod p$ 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.
$\left(\frac{p-a}{p}\right)= \left(\frac{-a}{p}\right)= \left(\frac{-1}{p}\right) \left(\frac{a}{p}\right)= (-1)^{\frac{p-1}{2}}$

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:
$\left( \frac{3}{p} \right)=(-1)^{\frac{3-1}{2}\cdot\frac{p-1}{2}}\left( \frac{p}{3} \right ) = (-1)^{2^{k-1}} \left( \frac{(-1)^k+1}{3} \right)$
If k>1 and k is even, then this number is equal to
$\left( \frac{2}{3} \right) = -1$
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:
$x^2+x-1=(x+2^{-1})^2-1-(2^{-1})^2=(x+6)^2-1-6^2=(x+6)^2-4=0 \mod 11$

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.

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
$x^3\equiv 8+3\cdot 4 \cdot 13y +3 \cdot 2\cdot (13)^2 y^2 \mod 13^3$
So we want to solve
$3\cdot 4 \cdot 13y +3 \cdot 2\cdot (13)^2 y^2 \equiv 0 \mod 13^3$
or equivalently
$12 y +6\cdot 13 y^2 \equiv 0 \mod 13^2$
This means that y=0 mod 13, i.e. y=13z. This translates to
$12 z \equiv 0 \mod 13$
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

$(6+13y)^3-8\equiv 6^3-8+3\cdot 6^2 \cdot 13y +3 \cdot 6\cdot (13)^2 y^2 \equiv 0 \mod 13^3$
(the term with 13^3y^3 is not included, because it is zero modulo 13^3)

or equivalently

$13\cdot 16+3\cdot 6^2 \cdot 13 y +3 \cdot 6\cdot 13^2 y^2 \equiv 0 \mod 13^3$
or
$16+3\cdot 6^2 y +3 \cdot 6\cdot 13 y^2 \equiv 0 \mod 13^2$

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
$16+3\cdot 6^2 (-4+13z) +3 \cdot 6\cdot 13 (-4+13z)^2 \equiv 0 \mod 13^2$
or equivalently
$256+3*6^2z \equiv 0 \mod 13$
or
$9+4z \equiv 0 \mod 13$
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
$f(x)=x^k+a_1x^{k-1}+\ldots+a_k$
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
$2^n\equiv 1 \mod 2^n-1$
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,
$4^{\frac{{p-1}{2}}=2^{p-1}\equiv 1 \mod p$
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.

Yet another solution:
$x^{51}=(x^3)^{17}$
so first you notice that the congruence
$y^{17}\equiv 1 \mod 137$
has 17 solutions and then for each solution y the congruence
$x^3\equiv y \mod 137$
has only one solution
$x\equiv y^{91}\mod 137$
(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
$x=\frac{-a\pm\sqrt{a^2-4b}}{2}$
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
$x^7\equiv 3 \mod 21$
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
$x\equiv 3 \mod 21$
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).

Q: 9.4 a) from jan 26:
$7^{1734250}\equiv 1660565 \mod 1734251$
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 FLT
$7^{m-1}\equiv 1 \mod m$
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
$x^{\phi(m)}=1 \mod m$
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:
$6x\equiv 5 (\mod 7)$
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
$\phi(8800)$

A:
$8800=2^{5}\times 5^{2}\times 11$
$\phi(8800)=(2^{5}-2^{4})(5^{2}-5^{1})(11^{1}-11^{0})=8800(1-\frac{1}{2})(1-\frac{1}{5})(1-\frac{1}{11})$

Q: 11.5 Find x that solves
$x\equiv 3 \mod 37$
and
$x\equiv 1 \mod 87$
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
$m=561=3\cdot 11\cdot 17$
the congruence
$a^{m-1}\equiv 1 \mod m$
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
$7^{1734250}\equiv 1660565 \mod 1734251$
holds, show that 1734251 is a composite (i.e. non-prime) number.
c) The congruence
$2^{52632}\equiv 1 \mod 52633$
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
$\overline{a_0a_1\ldots a_n}=a_n+10a_{n-1}+\ldots+10^n a_n$
i.e. the digits are a_0,a_1,...,a_n.

Then
$a_n+10a_{n-1}+\ldots+10^n a_n \equiv a_n+a_{n-1}+\ldots+a_n \mod 9$
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
$\pm 1 \mp 1 \equiv 0, 0 \pm 1\equiv \pm 1, \pm 1 + 0 \equiv \pm 1$
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
$0\leq a < 73$
with
$a\equiv 9^{794} \mod 73$
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
$1\cdot 2\cdot 3\cdot \ldots\cdot (p-1)$
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
$x^2 \equiv 2 (\mod 7)$
A:
$0^2\equiv 0, (\pm 1)^2 \equiv 1, (\pm 2)^2\equiv 4, (\pm 3)^2\equiv 2 \mod 7$
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
$x^{10}+y^{10}=11z^{10}$
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.
$x^{10}=(x^5)^2$
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
$a^2+(\frac{a^2-1}{2})^{2}=(\frac{a^2+1}{2})^{2}$
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
$a^2\equiv (\pm 1)^2\equiv 1 \mod 3$
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:
$y^2= x^2+x=x(x+1)$
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
$x=\pm a^2$
for some integer a. For the same reason
$x+1=\pm b^2$
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
$33^2 + 56^2 = 65^2 and 16^2 + 63^2 = 65^2$
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:
$(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2=(ad-bc)^2+(ac+bd)^2$
(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:
$(a^2+b^2)(c^2+d^2)(e^2+f^2)=[(ac-bd)^2+(ad+bc)^2](e^2+f^2)=[(ad-bc)^2+(ac+bd)^2](e^2+f^2)$
and now use the identity once again.

Q: Show that
$\gcd(10^n-1,10^m-1)=10^{\gcd(m,n)}-1$
for any natural numbers m,n.

A: We showed in class that if
$n\geq m$
then
$\gcd(10^n-1,10^m-1)=\gcd({10^{n-m}-1,10^m-1})$
Let's now divide n by m with remainder: n= qm+r. By applying the result above q times, we get that
$\gcd(10^n-1,10^m-1)=\gcd({10^r-1,10^m-1})$
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
$\gcd(10^{\gcd(m,n)}-1,0)=10^{\gcd(m,n)}-1$
Q:Find an integer solution of
$a^2+ab+b^2=3c^2$
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

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
$x=\frac{(1-m)^2-3}{1+m+m^2}=\frac{m^2-2m-2}{m^2+m+1}$
and
$y=m(x-1)+1=m( \frac{m^2-2m-2}{m^2+m+1}-1) +1=\frac{1-2m-2m^2}{m^2+m+1}$
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
$m^2=3n^2$
has no nonzero solutions

A: We can assume that gcd(m,n)=1, otherwise write
$m_1=\frac{m}{gcd(m,n)}, n_1=\frac{n}{gcd(m,n)}$
then
$gcd(m_1,n_1)=1, m_1^{2}=3n_1^{2}$
Now m_1 is divisible by three, so
$3n_1^{2}=m_1^{2}$
is divisible by 9, so n_1 is divisible by three. We get the contradictionh with the fact that
$gcd(m_1,n_1)=1$
Q: January 10 question4
Prove that if
$x^2+2y^2=z^2$
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
$x^2+2y^2$
is also even, so z is even and
$2y^2=x^2-z^2=(x-z)(x+z)$
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
$2y^2=x^2-z^2=(x-z)(x+z)$
is divisible by 4 and so y is even.

Q: January 10 question3
prove
$x^2 + 2y^2=z^2$
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
$\cos 20^o$
is irrational. (Hint:
$\cos 3\alpha = 4\cos^3\alpha - 3 \cos \alpha)$
A:

Applying the hint we find that
$x=\cos 20^o$
satisfies the equation
$\frac 12 = 4x^3-3x$
or, equivalently, 8x^3-6x-1=0. By a theorem we proved in class the only candidates for rational solutions of this equation are
$\pm 1, \pm \frac 12, \pm \frac 14, \pm \frac 18$
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
$x(x+1)=y^2$
and use that x, x+1 are relatively prime.

Q: Show that if
$\sqrt n$
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
$p_1^{2t_1}\cdot \ldots \cdot p_m^{2t_m}$
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,