A number theory problem

We know $123456789$ is a multiple of $3$ since the sum of its digits is $45$ , which is a multiple of $3$ itself. Hence, $2^{123456789}$ can be written as

$2^{123456789} = (2^{3})^{n} = 8^{n}$

where $n$ is some positive integer. Taking $8^{n}$ mod $7$ , we get

$2^{123456789} \equiv 8^{n} \equiv (7+1)^{n} \equiv 1^{n} \equiv \boxed{1} \pmod{7}$

Through trial and error, we can simply find that $2^3 \equiv 1 (mod 7)$ $2^{123456789} = (2^{3})^{4115263}$ $(2^{3})^{4115263} \equiv 1^{4115263} (mod 7)$ So, $2^{123456789} \equiv 1 (mod 7)$

$2^{123456789}$ = $2^{3*41152263}$ = ( $2^3$ ) $^{41152263}$ [ By laws of exponents- $a^{bc}$ = $(a^b)$ $^c$ ]

= $8^{41152263}$

Let as assume that 41152263= $\gamma$

Now, $8 \equiv 1 \pmod{7}$

=> $8^\gamma \equiv 1^\gamma \pmod{7}$ [ By laws of exponentiation in modular arithmetic- if $a \equiv b \pmod{p}$ , then $a^k \equiv b^k \pmod{p}$ ]

Now 1 raised to any power remains 1.

=> $8^\gamma \equiv 1 \pmod{7}$

From the above statement we can finally conclude that when $2^{123456789}$ is divided by 7, it leaves a remainder of 1.

Notice what I did. 123456789 / 7 = 17636684. Something.

Ignore the something and multiply 7 x 17636684 = 123456788 Now, 123456789 - 123456788 = 1

I was able to bypass the base and any modular congruence. Please post this solution as a breakthrough.

After several trial-and-error approaches I found that 2^9 ≡ 1 (mod 7). I also noticed that 123456789 is divisible by 9, so

(2^9)^(something) ≡ (1)^(something) ≡ 1 (mod 7).

[After reading other answers I realize that I missed the 2^3 ≡ 1 (mod 7) approach what had been more simple].

We can use Fermat's Little theorem to see that 2^6 is congruent to 1 (mod 7). The power = 123456789 leaves remainder 3 when divided by 6. Thus we have 2^(6*k)[FOR SOME INTEGER k) is congruent to 1 (mod 7) and 2^3 is congruent to 1 (mod 7). Thus we have 2^(123456789) is congruent to (1 x 1)=1 (mod 7).

2 is congruent to 2(mod7) 2^3 is congruent to 1(mod 7) Therefore remainder is 1

This method is longer than those I've seen; it focusses on patterns more.

From 2^x (where x<123456790), you can see that the remainders when dividing by 7 form a pattern:

For x = 1,2,3,4 ,

2^1= 2 where 2 mod 7 = 2,

2^2 = 4 where 4 mod 7 = 4,

2^3 = 8 where 8 mod 7 = 1,

2^4 = 16 where 16 mod 7 = 2.

This cycle, consisting of the three key components (the 2, 4 and 1) repeats until 2^123456789 is reached.

123456789 mod 3 is what we are interested in, since there are 3 different components in the pattern. By doing this, you are seeing if there is a remainder from the number of groups there are of these 3 components before the number 123456789. This remainder will guide us into finding the right remainder for the initial problem.

123456789 mod 3 = 0 therefore there are complete number of groups of the components 2, 4 and 1 before reaching 123456789.

Therefore the remainder of 2^123456789 is 1 (the final component in the group.)

Taking the last digit into consideration 9, we can have (2^9)=(2^3)^3 and 2^3=1(mod 7). So we can now have , 1^3=1.

Sum of 1+2+...+9 = n(n+1)/2 = 9×10/2 = 45 So as 45%3=0 (2)^3 has same remainder with that of (2)^123456789 2^3 % 7 = 1

$2^{123456789} \equiv 2^{123456789 \bmod \phi (7) } \equiv 2^{123456789 \bmod 6} \equiv 2^3 \equiv 8 \equiv 1$ ( $\bmod$ $7$ )

We can solve it by Fermat's Little theorem :: - "if P is a prime number and a is an integer where a is not divisible by P, then a^(p-1) is equivalent to 1 (Mod P)

We can find the remainders when various powers of 2 are divided by 7. Then, we can prove that they form a cycle.

I figured that any power of 2 divided by an odd integer would have 1 as the remainder.

2^123456789=8^41152263 =(7+1)^41152263 therefore, rem=1

It is of the form 8k +1. So just divide it by 7 to get the answer

2^133556789 --cosider 2^(last no. 9)÷7. Gives reminder as 1