Question

Show that 2^100 - 1 is divisible by 101. I thought to use Fermat's Litlle Theorem to solve this
x^p = x mod p but p must be a prime number.

Answer 1

FLT is correct way to go...IMHHO

\(x^{p } \equiv x \mod p \implies 2^{101} \equiv 2 \mod 101\)

the duh moment is use \(p = 101\). that prolly sorts you out.

from there look at the rules for subtracting, multiplying and exponent'ing residues. Or look below for my **possibly shιtty** suggestion :)

The simplest way to finish this off that i can think of uses the multiplication rule.

We also know that: \(2 \equiv 2 \mod 101 \)

And so the multiplication rule tells us that:

\( 2^{101} = 2 \times 2^{100} \equiv (2 \times n) \mod 101 \implies n = 1 \)


So we know that: \(2^{100} \equiv 1 \mod 101\), and: \(1 \equiv 1 \mod 101\)


Subtracting 2nd from 1st:

\(\implies 2^{100} -1 \equiv 0 \mod 101\)

QED :)

PS: the latex is not showing as i type so this might look terrible.

Answer 2

@celticcat your question has been answered, come online to see it ^_^

Answer 3

thanks