4
$\begingroup$

This question came in a competitive exam I took recently.

The last digit of LCM of $3^{2003} - 1$ and $3^{2003} + 1$ is

is there any strategy by which we can quickly determine the answer? I am hoping there is, since the question came in a timed competitive test.

$\endgroup$
9
$\begingroup$

The GCD of $x$ and $y$ divides $x-y$, hence the GCD $3^{2003}-1$ and $3^{2003}+1$ is either $1$ or $2$; it is easy to check that both numbers are even, so this GCD of these is 2.

The LCM of $x$ and $y$ multiplied by the GCD of $x$ and $y$ equals $x \times y$. So the LCM in question equals $\frac{(3^{2003}-1) \times (3^{2003}+1)}{2} = \frac{3^{4006}-1}{2}$.

$3^n \mod 20$ gives us the following sequence: $1, 3, 9, 7, 1, 3, 9, 7, \cdots$; hence $3^{4006} \mod 20 = 3^2 \mod 20 = 9$, and the answer is $\frac{9-1}{2} = 4$.

$\endgroup$
3
$\begingroup$

Hint $\ $ Their gcd is $2$ since for odd $\rm\:k,\ (k\!+\!1,k\!-\!1) = (k\!+\!1,2)=2.\:$ So their lcm = product$/2$. Determining the product$/2$ mod $10$ requires determing the product mod $20.\,$ But mod $20$ we have $\rm(3^n\!-\!1)(3^n\!+\!1) = 9^n\!-\!1 = 0,8,0,8\ldots$ by $\,9^2\! = 81\equiv 1.\,$ Thus $\rm\,9^{2003}\!-1 = \color{#C00}{8+20\,k},\,$ hence

$$\rm \frac{(3^{2003}\!-1)(3^{2003}\!+1)}2\, =\, \frac{9^{2003}\!-1}2\, =\ \color{#C00}{4+10\,k}\ \ \ has\ last\ digit = 4$$

$\endgroup$
1
$\begingroup$

By euclid's algorithm(http://en.wikipedia.org/wiki/Euclidean_algorithm), $\gcd (a,b)=\gcd (a,a-b)$. Here, $\gcd(3^{2003}+1,3^{2003}-1)=\gcd(3^{2003}+1,2)=2$ (since $3^{2003}+1$ is an even integer).LCM=$ab/\gcd= \frac{3^{4006}-1}{2}.$ Now $ 3^4=1\pmod{20} \implies (3^4)^{1001}.9=-11\pmod {20}\implies {3^{4006}-1}=-12\pmod{20}=8\pmod{20} \implies $ $\frac{3^{4006}-1}{2}=8/2=4$ is the last digit.

$\endgroup$
  • $\begingroup$ The OP wants LCM not GCD. $\endgroup$ – lhf Jul 3 '12 at 11:24
  • 1
    $\begingroup$ You need to determine the product mod 20, to determine the product/2 mod 10. $\endgroup$ – Bill Dubuque Jul 3 '12 at 17:09
  • $\begingroup$ As an example of what Bill Dubuque said, observe that (9-1)/2 = 4 but (19-1)/2 = 9. So to find the last digit of (x-1)/2, it is not enough to know the last digit of x. $\endgroup$ – ShreevatsaR Jul 4 '12 at 4:18
0
$\begingroup$

gcd($3^{2003}+1\ , 3^{2003}-1$) $$=gcd(3^{2003}+1\ , 2)\ as\ gcd(a,b)=gcd(a,a-b)\ and\ 3^{2003}+1\ -(3^{2003}-1)=2$$ =2 as $3^n-1$ is even for any natural number n.

So,lcm($3^{2003}+1\ , 3^{2003}-1$)= ($3^{2003}+1)(3^{2003}-1$)/gcd($3^{2003}+1,\ 3^{2003}-1$)=($3^{4006}-1)/2$

Now, using Euler's Totient Theorem, $a^\phi(m)≡1(mod\ m)$ where (a,m)=1

So, $a^{k\phi(m)+h}≡a^h(mod\ m)$

Here (3,10)=(3,100)=1

Now, $\phi(10)=phi(2)phi(5)=1*4=4\ and\ \phi(100)=10phi(10)=40$

4006≡6(mod 40)≡2(mod 4)

$3^{4006}≡3^6(mod\ 100)≡3^2(mod\ 10)$

So, $lcm(3^{2003}+1\ , 3^{2003}-1)≡(3^6-1)/2(mod\ 100)≡(3^2-1)/2(mod\ 10)≡14(mod\ 100)≡4(mod\ 10)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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