Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

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

share|improve this question
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. – Jyrki Lahtonen Jul 31 '11 at 6:32
I added an IMHO relevant tag. – Jyrki Lahtonen Jul 31 '11 at 6:42

5 Answers

up vote 5 down vote accepted

HINT:

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

share|improve this answer
My answer is 512.I used Diophantine equations to minimize a.Thank you for the suggestion. – Eisen Jul 31 '11 at 7:02
up vote 3 down vote

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

share|improve this answer
Nicer idea than the solution in Engel's book. – André Nicolas Jul 31 '11 at 6:56
@Andre: I don't have the book. What is the solution? – mixedmath♦ Jul 31 '11 at 7:20
@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}$. – André Nicolas Jul 31 '11 at 12:41
up vote 1 down vote

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.

share|improve this answer
up vote 0 down vote

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

share|improve this answer
How is this relevant to the question? – robjohn♦ Mar 27 at 9:19
up vote 0 down vote

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.