Anonymous
Anonymous asked in Science & MathematicsMathematics · 2 months ago

Modular arithmetic?

Prove that x^7 − x ≡ 0 (mod 42) for every x ∈ Z.

I know about Fermat's little theorem which states that for p prime, x^p-1 ≡ 1 (mod p) but am unsure how to apply it here

2 Answers

Relevance
  • ?
    Lv 6
    2 months ago

    x^7 - x = x(x^6 - 1)

    Let's look at x^6 - 1 mod 7

    FLT tells us that x^6 - 1 = 0 mod 7, so x^7 - x is always divisible by 7.

    Now look at x^7 - x mod 2

    If x is even so is x^7, so the difference is even, and = 0 mod 2.

    If x is odd, so is x^6, so the difference is even, and = 0 mod 2

    So x^7 - x is always divisible by 2.

    Now look at x^6 - 1 mod 3.

    FLT tells us that x^2 = mod 3, so (x^2)^3 = x^5 = 1 mod 3, and x^6 - 1 = 0 mod 3.

    So x^7 - x is always divisible by 3.

    Since it's divisible by 2, 3 and 7, it must be divisible by the LCM of 2, 3 and 7 = 42,

  • 2 months ago

    I'm not sure if you were the same anonymous person that asked this about 3 days ago, but there were a couple answers provided previously. To date, none of them has been picked as "Favorite Answer" however.

    You've stated Fermat's Little Theorem as:

    x^(p-1) ≡ 1 (mod p)

    But it can be stated equivalently as:

    x^p - x ≡ 0 (mod p)

    (Subtract 1 from the first statement and multiply everything by x to see why this is true.)

Still have questions? Get your answers by asking now.