Questions & explanations
1. Check if the equation x^2 + y^2 = 3z^2 has a non-zero rational solution using the Hasse principle.
First, over reals: we need x^2+y^2=3z^2. If z≠0, we can set z=1, then x^2+y^2=3, which has real solutions (e.g., x=√3, y=0). So real solvable. Over Q_2 (2-adics): we need to check if there is a solution mod powers of 2. Mod 2, equation becomes x^2+y^2≡z^2 mod 2. Since squares mod 2 are 0 or 1, we can find non-zero solutions? For example, x=1,y=0,z=1 gives 1≡1 mod2. So solvable mod 2. Over Q_3: mod 3, squares mod 3 are 0,1. Equation x^2+y^2≡0 mod3. If z≠0 mod3, then z^2≡1, so x^2+y^2≡1 mod3. Possible? x=1,y=0 gives 1 mod3, so works. So locally solvable everywhere. By Hasse principle, there is a rational solution. Indeed, x=1,y=1,z=√(2/3) not rational. Wait, that's not rational. Actually, we need a non-zero rational solution. Does one exist? The equation x^2+y^2=3z^2 has rational solutions? For example, x=1,y=1,z=√(2/3) not rational. But we can find rational: set z=1, then x^2+y^2=3. This is a circle of radius √3, which has rational points? Yes, (x,y)=(1,√2) no. Actually, rational points on x^2+y^2=3 exist? For example, (x,y)=(1,√2) not rational. But there is a rational point: (x,y)=(1
2. Compare the Brauer group of Q and the Brauer group of a number field with no real embeddings.
The Brauer group of Q is isomorphic to Z/2Z ⊕ (Q/Z) (excluding the place at infinity). For a number field with no real embeddings, there is no Z/2Z factor because there are no real places. So Br(K) is isomorphic to (Q/Z)^{(r_2)} where r_2 is the number of complex places? Actually, the exact sequence gives Br(K) ≅ (Q/Z)^{(r_2)}? Wait, careful: For a number field with r_1 real and r_2 complex places, Br(K) ≅ (Z/2Z)^{r_1} ⊕ (Q/Z)^{r_2}? No, the sum of invariants is zero, so the image of ⊕ Br(K_v) → Q/Z is onto, and kernel is Br(K). So Br(K) is isomorphic to (Z/2Z)^{r_1} ⊕ (Q/Z)^{r_2-1}? Actually, the exact sequence splits? Better: Br(K) ≅ (Z/2Z)^{r_1} ⊕ (Q/Z)^{r_2}? Let's recall: The Brauer group of a number field is isomorphic to (Q/Z)^{r_2} if r_1=0? I think it's (Q/Z)^{r_2} if there are no real places? Actually, the correct statement: Br(K) ≅ (Z/2Z)^{r_1} ⊕ (Q/Z)^{r_2}? No, the sum of invariants is zero, so the rank is r_1 + r_2 - 1? Wait, I'm mixing. For Q, r_1=1, r_2=0, Br(Q) ≅ Z/2Z ⊕ (Q/Z)? That's infinite. Actually, Br(Q) ≅ Q/Z ⊕ Z/2Z? The exact sequence: 0 → Br(Q) → Br(R) ⊕ ⊕_p
3. Describe the steps of Montgomery reduction for computing x mod n where n is odd and R=2^k > n.
Montgomery reduction computes x * R^{-1} mod n for x < nR. Steps: 1) Compute q = (x mod R) * n' mod R, where n' = -n^{-1} mod R. 2) Compute t = (x + q*n) / R. 3) If t >= n, subtract n. The result is t ≡ x*R^{-1} mod n. For example, n=7, R=8, n'=1 because 7*7=49≡1 mod 8? Actually n'=7 since 7*7=49≡1 mod 8. For x=10, q=(10 mod 8)*7 mod 8 = 2*7=14≡6 mod 8. t=(10+6*7)/8=(10+42)/8=52/8=6.5? Not integer, so adjust: need x < nR=56, 10<56. Actually 52/8=6.5 not integer, so error: x must be multiple of R? Wait, algorithm requires x < nR and x is multiple of R? No, x arbitrary. Let's redo: n=7, R=8, n'=7. x=10, q=(10 mod 8)*7 mod 8 = 2*7=14 mod 8=6. t=(10+6*7)/8 = (10+42)/8 = 52/8 = 6.5, not integer. So condition: x must be such that x+q*n is divisible by R. For x=10, it's not, so algorithm fails? Actually Montgomery reduction expects x to be the result of a multiplication, so x is usually less than nR and may not be multiple of R. The algorithm works because q is chosen to make x+q*n divisible by R. Let's compute: x+q*n = 10+42=52, 52 mod 8 = 4, not 0. So q should be (x * n') mod R? Wait, cor
4. Factor n=8051 using Pollard's rho with f(x)=x^2+1.
Start x=2, y=2. Step1: x=2^2+1=5, y=f(f(2))=f(5)=5^2+1=26. gcd(|5-26|,8051)=gcd(21,8051)=? 8051/21=383.38, gcd(21,8051)=? 8051 mod21=8051-21*383=8051-8043=8, 21 mod8=5, 8 mod5=3, 5 mod3=2, 3 mod2=1, so gcd=1. Step2: x=f(5)=26, y=f(f(26))=f(26^2+1=677) =677^2+1=458330 mod8051? 8051*56=450856, remainder 7474? Actually 458330-8051*56=458330-450856=7474. So y=7474. gcd(|26-7474|,8051)=gcd(7448,8051). 8051 mod7448=603, 7448 mod603=7448-603*12=7448-7236=212, 603 mod212=179, 212 mod179=33, 179 mod33=14, 33 mod14=5, 14 mod5=4, 5 mod4=1, gcd=1. Step3: x=f(26)=677, y=f(f(7474))=f(7474^2+1 mod8051). 7474^2=55860676, mod8051? 8051*6939=8051*6000=48,306,000; 8051*939=7,559,889; sum=55,865,889; remainder 55860676-55865889=-5213? Actually 55860676-55865889 = -5213, so mod = 8051-5213=2838? Wait compute properly: 8051*6939 = 8051*(7000-61)=8051*7000=56,357,000 minus 8051*61=491,111 gives 55,865,889. 55,860,676 - 55,865,889 = -5,213, so add 8051: 2838. So 7474^2+1 mod8051 = 2838+1=2839? Actually 7474^2 mod8051 = 2838, then +1 = 2839. So y=2839. gcd(|677-2839|,8051)=gcd(2162,8051). 8051 mod2162=8051-2
5. Give an example of a quadratic form that satisfies local solvability everywhere but has no rational solution (if possible).
For quadratic forms in at least 3 variables, the Hasse principle holds, so no such example exists. However, for quadratic forms in 2 variables (binary quadratic forms), the Hasse principle can fail. For example, the equation 2x^2 + 2y^2 = z^2? Actually, binary forms are like ax^2+by^2=0. Consider x^2 + y^2 = 0 over Q. Over reals, the only solution is x=y=0, so no non-zero real solution, so local condition fails. So no counterexample. Actually, there are examples where local solvability holds but global fails for binary forms? For instance, the equation x^2 + 2y^2 = 3? Over reals, yes. Over Q_2? Possibly. But binary forms are covered by the Hasse principle? Actually, the Hasse-Minkowski theorem applies to quadratic forms in any number of variables, but for 2 variables it's about representing zero. The form ax^2+by^2=0 has a non-zero solution iff -ab is a square in Q. This is a global condition. Local conditions: over reals, need a and b have opposite signs; over p-adics, need -ab to be a square in Q_p. The Hasse principle holds: if -ab is a square in all completions, then it is a squa
6. Give an example of a higher-degree Diophantine equation with infinitely many integer solutions.
The equation x^2 + y^2 = z^2 has infinitely many solutions, but that's degree 2. For higher degree, consider x^3 + y^3 = 2z^3? Actually, x^3 + y^3 = 2z^3 has solutions like (1,1,1) but maybe infinite? Not sure. A known example: x^4 + y^4 = z^2 has no non-zero solutions (Fermat). But x^4 + y^4 = 2z^2? That might have infinite? Actually, a better example: x^3 + y^3 = z^3 has none. So higher-degree often have few solutions. But there are equations like x^3 + y^3 = 9z^3? Not sure. Let's use a known one: x^5 + y^5 = z^5 has none. So it's hard to find infinite families. Actually, there is the equation x^3 + y^3 = 2z^3 has infinite? I recall that x^3 + y^3 = 2z^3 has solutions like (1,1,1) and (1,1,1) but maybe parametric? I think it's not infinite. Let's say: The equation x^3 + y^3 = z^3 has none. So I'll give a different example: x^2 + y^2 = z^3 has infinite solutions? For example, (2,2,2) because 4+4=8. But that's mixed degree. For pure higher-degree, it's rare. So I'll state: Most higher-degree equations have only finitely many solutions, by Faltings' theorem for curves of genus > 1.
7. How does the exact sequence for the Brauer group help in computing the Brauer group of a number field?
The exact sequence reduces the computation of Br(K) to understanding local Brauer groups and the sum map. Local Brauer groups are known: Br(R) = Z/2Z, Br(C)=0, and for a finite place v, Br(K_v) ≅ Q/Z. The sum map is surjective, so Br(K) is the kernel. Thus Br(K) is isomorphic to the group of tuples (a_v) in ⊕_v Br(K_v) such that sum a_v = 0 in Q/Z. This gives a concrete description: Br(K) ≅ (Z/2Z)^{r_1} ⊕ (Q/Z)^{r_2-1}? Actually, it's isomorphic to (Q/Z)^{r_2} if r_1=0? I need to be precise: The exact sequence splits, so Br(K) ≅ (Z/2Z)^{r_1} ⊕ (Q/Z)^{r_2-1}? Wait, the rank of the direct sum is r_1 + (infinite many finite places), but the sum map kills one copy of Q/Z. So Br(K) is huge. For example, Br(Q) ≅ Q/Z ⊕ Z/2Z? That's not correct; it's actually Q/Z ⊕ Z/2Z? I think it's Q/Z ⊕ (Z/2Z)? No, the exact sequence gives Br(Q) as an extension, but it's known that Br(Q) ≅ Q/Z ⊕ Z/2Z? Actually, Br(Q) is isomorphic to the direct sum of Q/Z and Z/2Z? That would be too big? I'm mixing. Let's just say the exact sequence is the key tool.
8. Give an example of the Montgomery ladder for k=5 (binary 101).
Start with R0 = O (point at infinity), R1 = P. For each bit from left to right: bit 1: R1 = R0+R1 = P, R0 = 2*R0 = O. Bit 0: R0 = R0+R1 = P, R1 = 2*R1 = 2P. Bit 1: R1 = R0+R1 = P+2P=3P, R0 = 2*R0 = 2P. After all bits, R0 = 2P, R1 = 3P. The result is R0 = 5P? Actually, the final result is R0 if the last bit is 0, else R1. Here last bit 1, so result is R1 = 3P? Wait, correct: For k=5 (101), the algorithm yields R0 = 2P, R1 = 3P, and since last bit is 1, output R1 = 3P? That's wrong. Actually, the standard Montgomery ladder outputs R0 = kP. Let me redo: Start R0=O, R1=P. For each bit: if bit=1: R1 = R0+R1, R0 = 2*R0; else: R0 = R0+R1, R1 = 2*R1. For 101: bit1: R1=O+P=P, R0=2O=O. bit0: R0=O+P=P, R1=2P=2P. bit1: R1=P+2P=3P, R0=2P=2P. End. Output R0 = 2P? That's not 5P. I'm mixing up. Actually, the correct algorithm: R0 = O, R1 = P. For i from highest to lowest: if bit=1: R0 = R0+R1, R1 = 2*R1; else: R1 = R0+R1, R0 = 2*R0. For 101: bit1: R0=O+P=P, R1=2P. bit0: R1=P+2P=3P, R0=2P. bit1: R0=2P+3P=5P, R1=6P. Output R0=5P. Yes.
9. Use Pollard's p-1 to factor n=8051 with B=5.
Compute M = 2^2 * 3 * 5 = 60. Choose a=2. Compute 2^60 mod8051. Use exponentiation: 2^10=1024, 2^20=1024^2=1048576 mod8051=1048576-8051*130=1048576-1046630=1946; 2^40=1946^2=3786916 mod8051=3786916-8051*470=3786916-3783970=2946; 2^60=2^40*2^20=2946*1946 mod8051. 2946*1946=5732916 mod8051=5732916-8051*712=5732916-5732312=604. Then gcd(604-1,8051)=gcd(603,8051). 8051/603=13.35, compute gcd: 8051 mod603=8051-603*13=8051-7839=212; 603 mod212=603-212*2=179; 212 mod179=33; 179 mod33=179-33*5=14; 33 mod14=5; 14 mod5=4; 5 mod4=1; 4 mod1=0, so gcd=1. Failed. Try a=3: 3^60 mod8051? Possibly gives factor. Actually 8051=97*83, p-1=96=2^5*3, q-1=82=2*41. With B=5, M=60, 96 divides 60? No, 96 does not divide 60. So method fails because p-1 has factor 2^5, but M only has 2^2. Increase B to 10: M includes 2^3? Actually B=10, primes 2,3,5,7: M=2^3*3^2*5*7=8*9*5*7=2520. 96 divides 2520? 2520/96=26.25, no. 96=2^5*3, need exponent 5 on 2, so B must be at least 32. So method fails for this n with small B.
10. What is a strong pseudoprime? Give an example base for which 91 is a strong pseudoprime.
A strong pseudoprime to base a is a composite number n that passes the Miller-Rabin test for that base. For n=91=7*13, n-1=90=2*45, s=1, d=45. Choose a=10: compute 10^45 mod 91. Use exponentiation: 10^2=100≡9, 10^4≡9^2=81, 10^8≡81^2=6561≡9? Actually 81^2=6561, 6561 mod 91: 91*72=6552, remainder 9. So pattern: 10^(2^k) ≡ 9 for k≥1? Then 10^45 = 10^(32+8+4+1) = 10^32*10^8*10^4*10^1 ≡ 9*9*9*10 = 7290 mod 91. 91*80=7280, remainder 10. So 10^45 ≡ 10 mod 91, not ±1. So 10 is not a witness. Try a=3: 3^45 mod 91? 3^6=729≡1 mod 91? 91*8=728, so 3^6≡1, then 3^45=3^(6*7+3)= (3^6)^7 * 3^3 ≡ 1*27=27 mod 91, not ±1. So 3 also not witness. Actually 91 is a strong pseudoprime to base 3? Check: 3^45 ≡ 27, not ±1. So fails. Wait, need a such that a^d ≡ 1 or a^{2^r d} ≡ -1. For n=91, s=1, so only check a^45 ≡ ±1 mod 91. a=10 gives 10, not ±1. a=3 gives 27. a=9: 9^45 = (9^3)^15 = 729^15 ≡ 1^15=1 mod 91? 9^3=729≡1 mod 91, so 9^45≡1, so 91 is a strong pseudoprime to base 9. So base 9 works.
11. Give an example of an ABC triple with high quality. What is quality?
Quality q(a,b,c) = log(c) / log(rad(abc)). Higher quality means c is large relative to rad. A famous high-quality triple is a=2, b=3^10*109 = 59049*109? Actually, known triple: a=2, b=3^10*109 = 59049*109=6436341? Wait, better: a=1, b=2^4*3^2*5^2*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*97? That's too long. Simpler: a=1, b=2^4*3^2*5^2*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*97? Actually, the triple 1 + 2^4*3^2*5^2*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*97 = 2^? No. A known high-quality triple: a=2, b=3^10*109, c=23^5? Let's use: a=1, b=2^4*3^2*5^2*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*97? That's too messy. Instead, give the triple (1, 8, 9) with rad=6, q=log9/log6≈1.226. Another: (1, 48, 49) rad=42, q=log49/log42≈1.041. The highest known quality is about 1.6299 from triple (2, 3^10*109, 23^5) but numbers are large.
12. Apply Vieta jumping to show that if a^2 + b^2 = 3(ab + 1) has positive integer solutions, then a = b = 2.
Assume (a, b) is a solution with a ≥ b > 0. Fix b and consider the quadratic in a: a^2 - 3b a + (b^2 - 3) = 0. One root is a, the other is a' = 3b - a. Vieta says a + a' = 3b, so a' is integer. Also a a' = b^2 - 3. If a > b, then a' = (b^2 - 3)/a < (b^2)/b = b, so a' < b. If a' > 0, we have a smaller positive solution (b, a'), contradicting minimality of a. The only way to avoid descent is a = b, then a^2 + a^2 = 3(a^2 + 1) gives 2a^2 = 3a^2 + 3, so a^2 = -3, impossible. But if a = b = 2, check: 4+4=8, 3(4+1)=15, not equal. Actually the equation has no positive solutions? Wait, let's check: a=1,b=1 gives 2=6, no. So the method shows no solutions except maybe trivial. Correct: The equation a^2 + b^2 = 3(ab+1) has no positive integer solutions. The descent argument leads to contradiction unless a=b, which fails. So answer: no solutions.