I'm having a lot of trouble figuring out this discrete math question:

What are the last four bits in the binary expansion of 1234^5555 + 4321 ^5555?

I need to add the two numbers and convert to binary. From what I know so far, to get the last bit from binary, you need to take mod 2. From this, to get the last four bits I understand that you need to take mod 16. However, I don't know how to efficiently take a mod of a very large number or convert a large number to binary.

I've also considered using Fermat's Little Theorem.

Can someone help me out or guide me along the right path?


1 Answer 1


$a^m \equiv b^m $ if $a \equiv b$. Thus, $1234^{5555} \equiv 2^{5555}$, which is definitely divisible by 16, so equal to 0 mod 16.

Now, what is 4321 mod 16? What is it when taken to power 5555?


Your Answer

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