Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prove that x^100 = 1 for all x in U(1000)

  1. Apr 8, 2008 #1
    1. The problem statement, all variables and given/known data

    Prove that x^100 = 1 for all x in U(1000)

    2. Relevant equations

    3. The attempt at a solution

    U(1000) is all numbers relatively prime to 1000. And that is as far as I have gotten.

  2. jcsd
  3. Apr 8, 2008 #2
    Are you sure you haven't missed a part of the problem....?

    x=1001 is relatively prime to 1000, but 1001^100 is not equal to one.
  4. Apr 8, 2008 #3
    Huh? Well U(1000) is all numbers less than a 1000 and relatively prime to 1000, that changes things, at least with your counter example...forgot to mention that
  5. Apr 8, 2008 #4
    What about 3, 7, etc? These are all relatively prime to 1000 (and also less than 1000), yet neither 3^100 nor 7^100 are equal to 1. You are most likely missing some part of the problem.

    Edit: You probably meant this - "Prove that x^100 = 1 mod(1000) for all x in U(1000)." Try using Euler's Theorem.
    Last edited: Apr 8, 2008
  6. Apr 9, 2008 #5
    Well that is the problem how it is stated...but the idiot I am keeps forgetting to mention all the details of U(n)....it is the group of units modulo n (that is the set of integers less than n and relatively prime to n under multiplication modulo n). But what you say is what I want.
    I for example take 3^100=1mod(1000) , 1000 should divide (3^100 - 1) but it does not, you end up with a decimal...so I cant even see what the problem looks like when you plug in a number to x
  7. Apr 9, 2008 #6
    It does divide 3^100 - 1. Not sure what you mean by getting a decimal. If you have Windows, try the built-in calculator and calculate 3^100 mod(1000). You'll get 1, which verifies the equation 3^100=1mod(1000). If you calculate 3^100 - 1 mod(1000), you will get 0, which means that 1000 evenly divides 3^100 - 1.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook