RMO 1991

If someone like my my solution vote up and please give solution to this Crazy functions!!!!

Fermat’s Little theorem:

If p is prime 

Then a^(p-1) = 1 (mod p)

Corollary: 

If p is a prime Then

a^p = a (mod. p) for any integer a.

Here 1990 = 199 x 10, 199 is prime number

On application

2^199 = 2 (mod 199)

==> 199 ⎪ 2^199 – 2

==> 199n = 2^199 – 2

==> 2^199 = 199n + 2

==> 2^1990 = (199n +2)^10

= (199n)^10 + 10c1 (199n)^9 . 2 + …. + 2^10

 ==> 2^1990 - 2^10   =   (199n)^10 + 10c1 (199n)^9 . 2 + …. + 10C9 (199n)^9 . 2

Here, we know the last – digit on power of 2 

    2^1, 2^5, 2^9, … =  2

2^2, 2^6, 2^10, … = 4

    2^3, 2^7, 2^11, … = 8

    2^4, 2^8, 2^12, … = 6

i.e last digit for 2^10, = 4

and last digit for 2^1990 = 4

2^(2+m . 4)

                        1990 = 2 + (497 x 4)

2^(2+497 x 4)

So, in 2^1990 – 2^10 both terms have last digit 4. Hence it,s difference has last digit 0 i.e. dividable by 10.

So 2^1990 – 2^10 is divisible by 10

Further 2^1990 – 2^10 is divisible by 199

So 2^1990 – 2^10 is divisible by 1990

So when 2^1990 is divided by 1990 andThe remainder will be 2^10

i.e. 1024

If someone like my my solution vote up and please give solution to this Crazy functions!!!!

Maybe this is an overkill and possibly I could shorten my solution so pls comment if you have any suggestions! :D

Solution:

Since $1990=2(5)(199)$ we will look split the question into smaller mods and then apply Chinese Remainder Theorem. Clearly, $2^{1999} \equiv 0 \pmod{2}$ .

Since $2^4 \equiv 1 \pmod{5}$ , we know $2^{1990} \equiv 2^2 \pmod {5} \equiv 4 \pmod {5}$

Now, calculating $2^{1990} \equiv \pmod{199}$ can be tough. In order to do that, we will use Euler's Theorem. Since $199$ is a prime, $\varphi(199)=199-1=198$ .

Therefore, $2^{198} \equiv 1 \pmod {199}$
$2^{1980} \equiv 1 \pmod {199}$ $2^{1990} \equiv 2^{10} \pmod{199} \equiv 29 \pmod{199}$

Now, let $X = 2^{1990} \pmod {1990}$ . Then, since $X \equiv 29 \pmod{1995}$ and $X \equiv 4 \mod 5$ , we have $X \equiv 29 \pmod {995}$ by Chinese Remainder Theorem. Since $X \equiv 0 \pmod{2}$ , we know by Chinese Remainder Theorem $X \equiv 1024 \pmod{1990}$ so $X = 1024$ . Hence, $2^{1990} \equiv 1024 \pmod {1990}$ .

Let N = 2^1990 Here, 1990 can be written as the product of two co-prime factors as 199 and 10. Let R1 ≡ MOD(21990, 199) According the the Fermet’s Theorem, MOD(ap, p) ≡ a . ∴ MOD(2199, 199) ≡ 2. ∴ MOD((2199)10, 199) ≡ MOD(210, 199) ∴ MOD(21990, 199) ≡ MOD(1024, 199) ≡ 29 ≡ R1. Let R2 ≡ MOD(21990, 10) ∴ R2 ≡ 2 × MOD(21989, 5) Cancelling 2 from both sides. Now, MOD(21989, 5) ≡ MOD(2 × 21988, 5) ≡ MOD(2, 5) × MOD((22)994, 5) Also MOD(4994, 5) ≡ (-1)994 = 1 & MOD(2, 5) ≡ 2 ∴ MOD(21989, 5) ≡ 2 × 1 ∴ R2 ≡ 2 × 2 = 4. ∴ N leaves 29 as the remainder when divided by 199 and 4 as the remainder when divided by 10. Let N1 be the least such number which also follow these two properties i.e. leaves 29 as the remainder when divided by 199 and 4 as the remainder when divided by 10 ∴ N1 ≡ 199p + 29 = 10q + 4 (where, p and q are natural numbers) ∴ 199p + 25 = q 10 Of course, the 5 is the least value of p at which the above equation is satisfied, Correspondingly, q = 102. ∴ N1 = 1024. ∴ Family of the numbers which leaves 29 as the remainder when divided by 199 and 4 as the remainder when divided by 10 can be given by f(k) = 1024 + k × LCM(199,10) = 1024 + k × 1990 N is also a member of the family. ∴ N = 21990 = 1024 + k × 1990 ∴ MOD(21990, 1990) ≡ 1024.

VBA code:

x = 1

For i = 1 To 1990

x = 2 * (x Mod 1990)

Next i

MsgBox (x)

Solve it with $mod$ function.

$2^{1990} mod$ $1990 = 1024$

Thus, the answer is $\boxed{1024}$