1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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