3
$\begingroup$

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

  • 0
    Presumably you want this to hold for **all** odd values of $n$? Is that period between $a$ and $23^n$ a multiplication sign? The TeX-code \cdot gives you that.2011-07-31
  • 0
    I added an IMHO relevant tag.2011-07-31

5 Answers 5

5

HINT:

1971 = 27 * 73. Use modular arithmetic and congruences.

  • 0
    My answer is 512.I used Diophantine equations to minimize a.Thank you for the suggestion.2011-07-31
3

Hint: $50^2\equiv 23^2\pmod{1971}$

  • 0
    Nicer idea than the solution in Engel's book.2011-07-31
  • 0
    @Andre: I don't have the book. What is the solution?2011-07-31
  • 0
    @mixedmath: $50^n+23^n a\equiv (-4)^n +(-4)^na\equiv -4^n(a+1) \pmod{27}$, $50^n+23^n a \equiv (-23)^n +23^n a \equiv 23^n(a-1)\pmod{73}$. Then standard solving of $a\equiv -1\pmod{27}$, $a\equiv 1\pmod{73}$.2011-07-31
1

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.

0

Find the smallest positive integer $n$ for: $$\left(\frac{1+j}{1-j}\right)^n =1;\quad (j^2 =-1)$$

  • 0
    How is this relevant to the question?2013-03-27
0

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} $$