1

Question

If today is Wednesday, what day of week will it be in 2^363 days?

Okay so I need some way to easily calculate 2^363 (modulus 7). I know that this can be done without the calculator. There are probably some super easy way to solve this, but I just can't do it.

Gustav Blomqvist
  • 113

2 Answers2

2

$\color\red{2^3}\equiv\color\red{1}\pmod7\implies$

$2^{363}\equiv2^{3\cdot121}\equiv(\color\red{2^3})^{121}\equiv\color\red{1}^{121}\equiv1\pmod7$

So it is $1$ day after Wednesday, meaning Thursday.

barak manos
  • 43,109
2

As always barak manos has the sleek and clever and simplest answer.

However you might want to read up on Fermat's Little Theorem which states:

if $p$ is prime, and $m$ is not a multiple of $p$ then $m^{p-1} \equiv 1 \mod p$ and $m^p \equiv p \mod p$.

So as $7$ is prime, and $2$ isn't a multiple of 7...

So by FLT $2^6 \equiv 1 \mod 7$ [*]and ...

$2^{363} = 2^{6*60 + 3} = (2^6)^{60}2^3 \equiv 1^{60}2^3 \equiv 1*8 \equiv 1 \mod 7$

So ... Thursday.

It's not as slick or as fast or easy as barak's but, well, .... it's a "big gun" that you will often pull out in the future.

Say, for instance, if instead of being asked what day of the week your were asked what day of the 29 day lunar cycle the day would fall on.

It'd be hard for find by trial and error that $2^{28} \equiv 1 \mod 29$ but FLT tells you that right away. Then it's a matter of $2^{363} = (2^{28})^{12}2^{15} \equiv 2^{15} \equiv (2^5)^3 \equiv 32^3 \equiv 3^3 \equiv 27 \mod 29$.

So that falls on Thursday, 27 days later (or 2 days earlier) in the lunar cycle.

[*] Post-script. Barak Manos pointed out that $2^3 \equiv 1 \mod 7$. FLT tells you $2^6 \equiv 1 \mod 7$. Why the difference? Well, FLT gives you one value of $n$ where $m^n \equiv 1 \mod p$. It doesn't claim to give you the smallest such number.

However, if $m^{p-1} \equiv 1 \mod p$ then $m^{\frac{p-1}2} \equiv \pm 1 \mod p$.

fleablood
  • 124,253