1.find last two digits of 2^1000

2.(a,a+k)/k for a,knot equel to 0

3.(a,b)=1 and c>0 prove that an integer sugh that (a+bx,c)=1(Headbang)

Printable View

- Aug 10th 2008, 12:54 AMvinodannunumber theory
1.find last two digits of 2^1000

2.(a,a+k)/k for a,knot equel to 0

3.(a,b)=1 and c>0 prove that an integer sugh that (a+bx,c)=1(Headbang) - Aug 10th 2008, 02:41 AMtopsquark
- Aug 10th 2008, 02:57 AMKiwi_DaveQ1
Start writing down the last two digits of the sequence of numbers $\displaystyle 2^1,2^2,2^3 $.

You will find that after every 20 entries the last two digits start to repeat. This is not surprising because the last two digits of $\displaystyle 16*2^{20} $ are 16.

Now you don't have to go all of the way up to 1000 because there is a clear pattern.

If we seek $\displaystyle 2^n$ then:

if n = 20X+1 then the last two digits are 52 (X>1)

For example the last digit of $\displaystyle 2^{441}$ is 52.

You can find the last two digits of $\displaystyle 2^{1000} $ in a similar way. - Aug 10th 2008, 10:13 AMJaneBennet
Note that $\displaystyle 2^{20}=1048576\equiv76\pmod{100}$

Now 76 is a good number to play with here because the last two digits of any of its positive powers are 76 (e.g. $\displaystyle 76^2=5776$, $\displaystyle 76^3=438976$, etc).

Hence $\displaystyle 2^{1000}=\left(2^{20}\right)^{50}\equiv76^{50}\pmo d{100}\equiv76\pmod{100}$.

So the last two digits of $\displaystyle 2^{1000}$ are 76.

Let $\displaystyle d=\gcd(a,a+k)$. Then $\displaystyle d\mid a$ and $\displaystyle d\mid a+k$.

$\displaystyle \therefore d\mid(a+k)-a=k$ - Aug 10th 2008, 11:06 AMJaneBennet
All right, this one is tricky, but I think we can prove the contrapositive statement instead: If $\displaystyle \gcd(a+bx,c)>1$ for all integers $\displaystyle x$, then $\displaystyle \gcd(a,b)>1$.

Let $\displaystyle \gcd(a+bx,c)=d>1$. Then $\displaystyle d\mid a+bx$ for all $\displaystyle x\in\mathbb{Z}$. In particular, $\displaystyle d\mid a=a+b\cdot0$. Hence, by the result in part 2, $\displaystyle d\mid bx$ for all $\displaystyle x\in\mathbb{Z}$; in particular, $\displaystyle d\mid b=b\cdot1$.

So $\displaystyle d\mid a$ and $\displaystyle d\mid b$. $\displaystyle \therefore\ \gcd(a,b)\ge d>1$. - Aug 10th 2008, 08:44 PMNonCommAlg
this is not true because $\displaystyle d$ and $\displaystyle x$ are dependent. the problem is strangely tricky! here's my proof which is constructive: we'll consider two cases:

__Case 1__every prime divisor of $\displaystyle c$ divides $\displaystyle a$: let $\displaystyle x=1$ and suppose $\displaystyle p$ is a prime divisor of $\displaystyle c.$ if $\displaystyle p | a+b,$ then $\displaystyle p|b,$ which is impossible because then $\displaystyle p|\gcd(a,b)=1.$ thus $\displaystyle \gcd(a+b,c)=1.$

__Case 2__some prime divisors of $\displaystyle c$ do not divide $\displaystyle a$: let $\displaystyle x$ be the product of all prime divisors of $\displaystyle c$ that do not divide $\displaystyle a.$ now let $\displaystyle p$ be a prime divisor of $\displaystyle c$ and suppose that $\displaystyle p|a+bx. \ \ \ (1)$

__subcase1:__if $\displaystyle p|a,$ then by (1): $\displaystyle p|bx.$ then since $\displaystyle \gcd(a,b)=1,$ we must have $\displaystyle p|x,$ which is impossible by the definition of $\displaystyle x.$

__subcase 2:__if $\displaystyle p$ does not divide $\displaystyle a,$ then by the definition of $\displaystyle x$ we'll have $\displaystyle p|x$ and thus by (1): $\displaystyle p|a,$ which is a contradiction! thus $\displaystyle \gcd(a+bx,c)=1. \ \ \ \square$