Finding the smallest positive integer a Can we find the smallest positive integer $a$ such that $1971|50^n+a.23^n$ where n is odd?
Source:Problem Solving Strategies by Arthur Engel
 A: HINT:
1971 = 27 * 73. Use modular arithmetic and congruences.
A: Hint: $50^2\equiv 23^2\pmod{1971}$
A: For coprime $\rm\: b,c\in \mathbb Z\:,\ \  a\: =\: -(b/c)^{2\:k+1} =\: -(b^2/c^2)^{k}\ b/c\: \equiv\: -b/c \pmod{b^2-c^2}\:.\:$
So the extended Euclidean algorithm will efficiently  compute $\rm\:a \equiv -b/c\pmod{b^2-c^2}\:.$    
Alternatively note $\rm\:a\equiv -1\pmod{b-c}$ since then $\rm\  b\equiv c\ \Rightarrow\ a = -b/c \equiv -c/c\equiv -1\:.\: $
Similarly we infer $\rm\ a\:\equiv\ 1\ \pmod{b+c}\:.\:$ When  $\rm\:b,c\:$ have opposite parity, $\rm\:b-c,\ b+c\:$ are coprime, so we may employ $\rm CRT$ to efficiently  compute the unique solution $\rm\: (mod\ \ b^2-c^2)\:.$  
Such nontrivial $(\ne \pm 1)$ square-roots of $1\:$  exist modulo composite $\rm\:m\:$ that are not prime powers. In fact, given such a nontrivial square root $\rm\:a\:$ one may  compute a factor of $\rm\:m\:$ by $\rm\:gcd(a\pm1,m)\:,\:$ e.g. above $\rm\ a = 512,\ \ gcd(511,1971) = 73,\ \ gcd(513,1971) = 27\:.\:$ This is the way many integer factoring algorithms work, e.g. Fermat's method of difference of squares and its generalizations, e.g. MPQS. See here for more on relations between factorization, nontrivial sqrts and idempotents.
A: Find the smallest positive integer $n$ for: $$\left(\frac{1+j}{1-j}\right)^n =1;\quad (j^2 =-1)$$
A: Since $50^2\equiv23^2\equiv529\pmod{1971}$ and $(529,1971)=1$, we have
$$
\begin{align}
50^{2n+1}+a\cdot23^{2n+1}&\equiv0\pmod{1971}\\
50\cdot529^n+a\cdot23\cdot529^n&\equiv0\pmod{1971}\\
50+a\cdot23&\equiv0\pmod{1971}
\end{align}
$$
Using the Euclid-Wallis Algorithm
$$
\begin{array}{r}
&&85&1&2&3&2\\\hline
1&0&1&-1&3&-10&23\\
0&1&-85&86&-257&857&-1971\\
1971&23&16&7&2&1&0\\
\end{array}
$$
we get that $857\cdot23\equiv1\pmod{1971}$. Therefore,
$$
a\equiv-50\cdot857\equiv512\pmod{1971}
$$
