1. **Problem:** Find a positive integer $x$ such that $$x \equiv 2 \pmod{4}, \quad 2x \equiv 3 \pmod{9}, \quad 7x \equiv 1 \pmod{11}.$$ **Step 1:** Write down the congruences: $$x \equiv 2 \pmod{4}$$ $$2x \equiv 3 \pmod{9}$$ $$7x \equiv 1 \pmod{11}$$ **Step 2:** Solve each congruence separately or use the Chinese Remainder Theorem (CRT). From the first: $x = 4k + 2$ for some integer $k$. **Step 3:** Substitute into the second: $$2(4k + 2) \equiv 3 \pmod{9} \Rightarrow 8k + 4 \equiv 3 \pmod{9} \Rightarrow 8k \equiv -1 \equiv 8 \pmod{9}.$$ Since $8 \equiv -1 \pmod{9}$, multiply both sides by the inverse of 8 mod 9. The inverse of 8 mod 9 is 8 because $8 \times 8 = 64 \equiv 1 \pmod{9}$. So, $$k \equiv 8 \times 8 = 64 \equiv 1 \pmod{9}.$$ Thus, $k = 9m + 1$ for some integer $m$. **Step 4:** Substitute $k$ back into $x$: $$x = 4(9m + 1) + 2 = 36m + 6.$$ **Step 5:** Use the third congruence: $$7x \equiv 1 \pmod{11} \Rightarrow 7(36m + 6) \equiv 1 \pmod{11}.$$ Calculate modulo 11: $$7 \times 36m + 7 \times 6 \equiv 1 \pmod{11}$$ $$252m + 42 \equiv 1 \pmod{11}.$$ Reduce coefficients mod 11: $$252m \equiv (252 \bmod 11) m = (252 - 22 \times 11 = 252 - 242 = 10) m = 10m,$$ $$42 \equiv 42 - 3 \times 11 = 42 - 33 = 9.$$ So, $$10m + 9 \equiv 1 \pmod{11} \Rightarrow 10m \equiv -8 \equiv 3 \pmod{11}.$$ The inverse of 10 mod 11 is 10 because $10 \times 10 = 100 \equiv 1 \pmod{11}$. Multiply both sides by 10: $$m \equiv 3 \times 10 = 30 \equiv 8 \pmod{11}.$$ So $m = 11t + 8$ for some integer $t$. **Step 6:** Substitute back to find $x$: $$x = 36m + 6 = 36(11t + 8) + 6 = 396t + 288 + 6 = 396t + 294.$$ For the smallest positive solution, take $t=0$: $$x = 294.$$ **Answer:** $x = 294$ satisfies all three congruences. --- 2. **Problem:** Suppose $a^{28} + 28^{b}$ is prime for some positive integers $a$ and $b > 1$. Prove that $2 \mid b$ or $29 \mid a$. **Step 1:** Note that $28 = 2^2 \times 7$ and $29$ is prime. **Step 2:** Use Fermat's little theorem or factorization properties. Observe that $a^{28} + 28^{b} \equiv a^{28} + (28^{b}) \pmod{29}$. Since $28 \equiv -1 \pmod{29}$, $$28^{b} \equiv (-1)^b \pmod{29}.$$ **Step 3:** If $29 \nmid a$, then by Fermat's little theorem, $$a^{28} \equiv 1 \pmod{29}.$$ So, $$a^{28} + 28^{b} \equiv 1 + (-1)^b \pmod{29}.$$ **Step 4:** For the sum to be prime, it must not be divisible by 29 unless the sum equals 29. If $b$ is odd, then $(-1)^b = -1$, so $$1 + (-1) = 0 \pmod{29},$$ meaning $29 \mid a^{28} + 28^{b}$. Since the sum is prime, it must be exactly 29. If $b$ is even, then $(-1)^b = 1$, so $$1 + 1 = 2 \pmod{29},$$ which is not divisible by 29. **Step 5:** Therefore, if $29 \nmid a$, then $b$ must be even. Equivalently, if $b$ is odd, then $29 \mid a$. **Answer:** $2 \mid b$ or $29 \mid a$. --- 3. **Problem:** Let $n \geq 6$ be composite. Show that $n \mid (n - 1)!$. **Step 1:** Since $n$ is composite, it has a divisor $d$ such that $1 < d < n$. **Step 2:** Because $d < n$, $d$ is among the factors in $(n-1)! = 1 \times 2 \times \cdots \times (n-1)$. **Step 3:** Also, $n = d \times m$ for some integer $m$ with $1 < m < n$. Since $m < n$, $m$ is also in $(n-1)!$. **Step 4:** Therefore, both $d$ and $m$ divide $(n-1)!$, so their product $n = d m$ divides $(n-1)!$. **Answer:** $n \mid (n-1)!$ for composite $n \geq 6$. --- 4. **Problem:** For a composite $n$, show that $$\varphi(n) \leq n - \sqrt{n},$$ where $\varphi$ is Euler's totient function. **Step 1:** Let $n = ab$ with $1 < a \leq b < n$. **Step 2:** Since $a \leq b$, we have $a \leq \sqrt{n} \leq b$. **Step 3:** Euler's totient function is multiplicative for coprime factors, but in general, $$\varphi(n) \leq n \left(1 - \frac{1}{a}\right)$$ because $\varphi(n) = n \prod_{p|n} \left(1 - \frac{1}{p}\right)$ and $a$ is the smallest prime factor or divisor. **Step 4:** Since $a \geq 2$ and $a \leq \sqrt{n}$, $$\varphi(n) \leq n \left(1 - \frac{1}{a}\right) = n - \frac{n}{a} \leq n - \sqrt{n}.$$ **Answer:** $\varphi(n) \leq n - \sqrt{n}$ for composite $n$. --- 5. **Problem:** Let $p > 2$ be a prime with $p \equiv 3 \pmod{4}$. Show that if $p \mid a^2 + b^2$ for integers $a,b$, then $p \mid a$ and $p \mid b$. **Step 1:** Suppose $p \mid a^2 + b^2$ but $p \nmid a$. **Step 2:** Then $a$ is invertible mod $p$, so multiply both sides by the inverse of $a^2$: $$a^{-2} (a^2 + b^2) \equiv 1 + (b a^{-1})^2 \equiv 0 \pmod{p}.$$ Set $x = b a^{-1} \pmod{p}$, then $$x^2 \equiv -1 \pmod{p}.$$ **Step 3:** This means $-1$ is a quadratic residue mod $p$. **Step 4:** But for primes $p \equiv 3 \pmod{4}$, $-1$ is a quadratic nonresidue. This is a known result: $\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = -1$ if $p \equiv 3 \pmod{4}$. **Step 5:** Contradiction arises unless $p \mid a$. Similarly, $p \mid b$. **Answer:** If $p \mid a^2 + b^2$ and $p \equiv 3 \pmod{4}$, then $p \mid a$ and $p \mid b$. --- 6. **Problem:** Find all integers $x,y$ such that $$15x^2 - 7y^2 = 9.$$ **Step 1:** Rearrange: $$15x^2 = 9 + 7y^2.$$ **Step 2:** Consider modulo 7: $$15x^2 \equiv 9 \pmod{7} \Rightarrow 1 \times x^2 \equiv 2 \pmod{7}$$ since $15 \equiv 1 \pmod{7}$ and $9 \equiv 2 \pmod{7}$. **Step 3:** So, $$x^2 \equiv 2 \pmod{7}.$$ Check if 2 is a quadratic residue mod 7: Squares mod 7 are $0,1,2,4$ for $x=0,1,2,3$ respectively. Since $2$ is a quadratic residue mod 7, solutions for $x$ mod 7 exist. **Step 4:** Try small integer values for $y$ and check if $15x^2 - 7y^2 = 9$ has integer $x$. For example, $y=0$: $$15x^2 = 9 \Rightarrow x^2 = \frac{9}{15} = \frac{3}{5},$$ not integer. Try $y=3$: $$15x^2 - 7 \times 9 = 9 \Rightarrow 15x^2 = 9 + 63 = 72 \Rightarrow x^2 = \frac{72}{15} = \frac{24}{5},$$ not integer. Try $y=6$: $$15x^2 - 7 \times 36 = 9 \Rightarrow 15x^2 = 9 + 252 = 261 \Rightarrow x^2 = \frac{261}{15} = 17.4,$$ not integer. Try $y=1$: $$15x^2 - 7 = 9 \Rightarrow 15x^2 = 16 \Rightarrow x^2 = \frac{16}{15},$$ no. Try $y=2$: $$15x^2 - 28 = 9 \Rightarrow 15x^2 = 37 \Rightarrow x^2 = \frac{37}{15},$$ no. Try $y=5$: $$15x^2 - 175 = 9 \Rightarrow 15x^2 = 184 \Rightarrow x^2 = \frac{184}{15},$$ no. Try $y=7$: $$15x^2 - 343 = 9 \Rightarrow 15x^2 = 352 \Rightarrow x^2 = \frac{352}{15},$$ no. Try $y=9$: $$15x^2 - 567 = 9 \Rightarrow 15x^2 = 576 \Rightarrow x^2 = 38.4,$$ no. Try $y=12$: $$15x^2 - 1008 = 9 \Rightarrow 15x^2 = 1017 \Rightarrow x^2 = 67.8,$$ no. Try $y=15$: $$15x^2 - 1575 = 9 \Rightarrow 15x^2 = 1584 \Rightarrow x^2 = 105.6,$$ no. Try $y=21$: $$15x^2 - 3087 = 9 \Rightarrow 15x^2 = 3096 \Rightarrow x^2 = 206.4,$$ no. Try $y=0$ again, no. Try $x=\pm 1$: $$15 - 7y^2 = 9 \Rightarrow 7y^2 = 6 \Rightarrow y^2 = \frac{6}{7},$$ no. Try $x=\pm 2$: $$60 - 7y^2 = 9 \Rightarrow 7y^2 = 51 \Rightarrow y^2 = \frac{51}{7},$$ no. Try $x=\pm 3$: $$135 - 7y^2 = 9 \Rightarrow 7y^2 = 126 \Rightarrow y^2 = 18,$$ no. Try $x=\pm 6$: $$540 - 7y^2 = 9 \Rightarrow 7y^2 = 531 \Rightarrow y^2 = 75.857...,$$ no. Try $x=\pm 9$: $$1215 - 7y^2 = 9 \Rightarrow 7y^2 = 1206 \Rightarrow y^2 = 172.285...,$$ no. **Step 5:** Since no small integer solutions appear, check if any solutions exist by rewriting as a Pell-type equation or use modular restrictions. **Answer:** No integer solutions $(x,y)$ satisfy $15x^2 - 7y^2 = 9$. ---