# number theory

• August 10th 2008, 12:54 AM
vinodannu
number 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)
• August 10th 2008, 02:41 AM
topsquark
Quote:

Originally Posted by vinodannu
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)

I'll leave all of this to the experts, but 2 and 3 are not written clearly. I don't know what 2) is asking for at all, and for 3) if we set x = 0 and c = b then we have found such an x. It seems too trivial.

-Dan
• August 10th 2008, 02:57 AM
Kiwi_Dave
Q1
Start writing down the last two digits of the sequence of numbers $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 $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 $2^n$ then:

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

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

You can find the last two digits of $2^{1000}$ in a similar way.
• August 10th 2008, 10:13 AM
JaneBennet
Quote:

Originally Posted by vinodannu
1.find last two digits of 2^1000

Note that $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. $76^2=5776$, $76^3=438976$, etc).

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

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

Quote:

Originally Posted by vinodannu
2.(a,a+k)/k for a,knot equel to 0

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

$\therefore d\mid(a+k)-a=k$
• August 10th 2008, 11:06 AM
JaneBennet
Quote:

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

All right, this one is tricky, but I think we can prove the contrapositive statement instead: If $\gcd(a+bx,c)>1$ for all integers $x$, then $\gcd(a,b)>1$.

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

So $d\mid a$ and $d\mid b$. $\therefore\ \gcd(a,b)\ge d>1$.
• August 10th 2008, 08:44 PM
NonCommAlg
Quote:

Originally Posted by JaneBennet

Let $\gcd(a+bx,c)=d>1$. Then $d\mid a+bx$ for all $x\in\mathbb{Z}$.

this is not true because $d$ and $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 $c$ divides $a$: let $x=1$ and suppose $p$ is a prime divisor of $c.$ if $p | a+b,$ then $p|b,$ which is impossible because then $p|\gcd(a,b)=1.$ thus $\gcd(a+b,c)=1.$

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

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

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