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!

Could someone please check this proof-mods!

  1. Apr 21, 2012 #1
    1. The problem statement, all variables and given/known data
    In the following questions you are given a theorem , together with the basic ideas needed to prove it. Write up a detailed proof of the Theorem. Your answer must be written in complete sentences, with correct spelling and grammar. It must include a suitable introduction and conclusion; reasons for all statements made; correct logical flow; and any necessary algebraic details.

    Theorem. if [itex] x^3 +x^2 +x +2 = 0 mod 5 [/itex], then [itex] x=1 mod 5[/itex]

    Basic ideas. if [itex] x=0,2,3,4 [/itex] [itex] mod 5[/itex] then [itex] x^3 +x^2 +x +2=2,1,1,1[/itex] [itex] mod 5.[/itex]



    2. Relevant equations



    3. The attempt at a solution

    [itex] x^3 +x^2 +x +2 = 0 [/itex] [itex] mod 5 [/itex], then [itex] x=1 [/itex] [itex] mod 5[/itex]

    To start consider when [itex] x=0,1,2,3,4 [/itex] Since in [itex] mod 5 [/itex]

    By exhaustion of cases we show show that [itex] x=1[/itex] is the only solution.

    Now when [itex] x=0 [/itex]

    [itex]0+0+0+2 =2 \neq 0 [/itex] [itex] mod 5[/itex]

    [itex]x=1[/itex]

    [itex]1+1+1+2 =5 = 0[/itex] [itex] mod 5[/itex]

    [itex]x=3[/itex]

    [itex]27+9+3+2 =31 \neq 0[/itex] [itex] mod 5[/itex]

    [itex]x=4[/itex]

    [itex]64+16+4+2 = 86 \neq 0[/itex] [itex] mod 5 [/itex]

    Hence[itex] x=1 [/itex] [itex] mod 5 [/itex]

    Is the only solution to [itex] x^3+x^2+x=2 = 0 [/itex] [itex]mod 5 [/itex]

    end of proof.

    Is this correct?
     
    Last edited: Apr 22, 2012
  2. jcsd
  3. Apr 22, 2012 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You forgot to do x=2 but otherwise that looks good
     
  4. Apr 22, 2012 #3
    No. You prove that it's good when x = 1, but nothing about how with x = 6 it's the same thing. What you should do is say x = 5n + y, then show that the result is equal to something divisible by 5 + the equation you were given.
     
  5. Apr 22, 2012 #4
    But x=6 mod 5 is the same as x=1 mod 5. So I only need to check cases x=0,1,2,3,4. I think!
     
  6. Apr 22, 2012 #5

    Ohh yeah when x=2, oops!
     
  7. Apr 22, 2012 #6
    6 = 1 mod 5, but that doesn't mean that for just any function f, f(6) = f(1) mod 5. You need to show that [itex]x^3 +x^2 +x +2[/itex] has that nice property (you could also prove that all polynomials have it).
     
  8. Apr 22, 2012 #7
    Im confused thoe, have I not done that by subing all values of x=1mod5 into f? thats why I checked when x=0,1,2....etc.
     
  9. Apr 23, 2012 #8
    Consider a silly function g(x) = 0 if x is even and 1 if x is odd. Now, let's see if g(6) = g(1) mod 5. Clearly, g(1) = 1 and g(5+1) = 0, so that property is not true and finding the values of g at 0, 1, 2, 3, 4 says nothing about its value with some other x.
    You're assuming the same property for your polynomial. Unless you take it as an axiom in your class, you can't assume things without proof.
     
  10. Apr 23, 2012 #9
    But I dont think we are really trying to prove if the polynomial is odd or even? and if I did consider all cases where x is congruent to 1 mod 5 the set would be infinite.
    So how should the correct proof look? because office shreder said it was ok?
     
  11. Apr 23, 2012 #10

    Curious3141

    User Avatar
    Homework Helper

    Your proof can easily be fixed by writing the cases as x = 0 (mod 5), x = 1 (mod 5), ... etc.

    If you simply wrote x =0, 1, 2, 3, 4, it's incomplete because x can take values lower or higher than that range.

    It's just a matter of presentation. Make it explicit that every case you're testing is an equivalence class modulo 5, and not just a single value of x.
     
  12. Apr 23, 2012 #11

    Curious3141

    User Avatar
    Homework Helper

    It's generally OK to assume that [itex]a \equiv b \pmod{m} \Rightarrow a^n \equiv b^n \pmod{m} \forall n \in \mathbb{N}[/itex]. I would say that's one of the basic axioms in modular arithmetic.
     
  13. Apr 23, 2012 #12

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Yes, it is generally ok, but I find it troubling that the OP doesn't see the problem.
     
  14. Apr 23, 2012 #13
    Ok so should I make it a little more like this....

    x^3+x^2+x+2= 0(mod 5)
    = 1 (mod5)
    = 2(mod5)
    = 3 (mod5)
    = 4 (mod5)


    and the test cases of x = 1,2,3,4,5
    but why stop at these x terms, surely I dont have consider every x?
     
  15. Apr 23, 2012 #14

    Curious3141

    User Avatar
    Homework Helper

    What you're writing here is poorly formatted and meaningless.

    What you should be writing is, to prove that [itex]x^3+x^2+x+2= 0 \pmod{5} \Rightarrow x = 1 \pmod{5}[/itex], a test of the values [itex]x = 0,1,2,3,4 \pmod{5}[/itex] is sufficient. The reason for this is every integer value of x can be expressed as some value between 0 and 4 (modulo 5).

    Then just proceed as you originally did.


    Again, don't forget you're NOT testing individual values of x (that's the way you wrote it there). With each case, you're testing a single congruence class modulo 5. Do you understand the difference?

    And why x = 1,2,3,4,5 (mod 5)? Not that it's wrong, but it's more work (calculation) than testing x = 0,1,2,3,4 (mod 5)? Isn't this what you'd originally done?

    I thought you'd already understood this part. Maybe not.

    Do you know the difference between these two expressions?

    1) [itex]x = 1 \pmod{5}[/itex]

    and

    2) [itex]x = 1[/itex]

    ?

    Please write a clear explanation so we can assess your understanding.
     
  16. Apr 24, 2012 #15

    Ok I have not been thinking correctly at all.

    So it should be along these lines

    consider when x=p modulo 5

    Since in modulo 5, consider,

    for p= 0,1,2,3,4.

    So now solving for

    p modulo 5 = x^3+x^2+x+2=0 modulo5

    when x=1

    1+1+1+2=5 =0 modulo 5

    so x=1 modulo 5

    end of proof?
     
  17. Apr 24, 2012 #16

    Curious3141

    User Avatar
    Homework Helper

    Unnecessary to introduce another variable p, but whatever.

    That doesn't make any sense! *Why* are you equating p (mod 5) to the polynomial in x (marked in red).

    I thought you meant p to represent the different residues x could give modulo 5. So why should that be equal to the entire polynomial?

    Forget about "p". Just:

    1) State that any integer x can be expressed as exactly one of 0,1,2,3,4 (modulo 5).

    2) Hence an exhaustive test will be done with each of those cases, i.e. test x = 0(mod 5), then x = 2(mod 5), x = 3(mod 5) and finally x = 4(mod 5).

    3) In doing the testing, just do the exponentiation and addition the usual way, since those rules of algebra apply in modular arithmetic too.

    4) After testing each of the cases, make the observation that only x = 1(mod 5) satisfied x^3 + x^2 + x + 2 = 0(mod 5). Hence x^3 + x^2 + x + 2 = 0(mod 5) IMPLIES x = 1(mod 5), and the proposition is proven.

    What about the other cases?

    Look, I really hope you understand what's meant by a modulo. You didn't reply to my earlier request/suggestion that we assess your understanding of the difference between:

    x = 1

    and

    x = 1 (mod 5).

    Are you confident you understand exactly what's going on when you see that (mod 5)?
     
  18. Apr 24, 2012 #17
    x=1 (is the number assigned to the vairiable x, where 1 is a point on the real number line.)

    x=1 (mod 5) (x can take on any real number, such that x-1= 5k for some integer k.)

    In this polynomial x^3 +x^2+x+2= 0 modulo 5

    do I need to only find one case where this is true or all cases?

    ie I can see that when x=1,then,

    1+1+1+2=5 = 0 mod5

    but surely it does not only apply when x=1 that x^3+x^2+x+2=0 mod5 is satisfied.

    Im assuming I only need to find one case where x^3+x^2+x+2=0 mod5, since for any multiple of 5 this is true.

    So why do I need to check other cases? If I have shown it is true for x=1 such that

    1+1+1+2=5=0 mod5 and therefore 1-1=5(0) then is it not true for any x that satisfies x-1=5k that it will then satify x^3+x^2+x+2=0 mod5.??

    I think I might be confused as to what is meant by x=1 mod5.

    as my understanding this means that x-1= 5k for some integer k.

    so when x=1 then 1-1=5(0) which is true.

    But is this the right line of thinking?
     
  19. Apr 24, 2012 #18

    Curious3141

    User Avatar
    Homework Helper

    Good. Your understanding is sound (except that x has to be an integer, not "any real number"). Basically, x = 1 means that x IS the actual number 1. x = 1 (mod 5) means (loosely) that when you divide x by 5, you get a remainder of 1. More formally, it means that x is of the form 5k + 1, where k is an integer (positive, negative or zero). This is the same as what you wrote (just rearrange).

    x = 1 is clearly one number that satisfies the property x = 1 (mod 5), it occurs when k is zero. But there are an infinite number of integers that satisfy that property.

    Now that we're done with the basics :smile:, let's move on.

    Let's call that polynomial P(x), shall we? P(x) = x^3 + x^2 + x + 2

    You need to prove that in all cases where P(x) = 0 (mod 5), it also follows that x = 1 (mod 5).

    The simplest way to do this is by exhaustion of cases, since there are so few.

    First, enumerate the possibilities. x can be any integer, positive, negative or zero. But in every single case, x (mod 5) can only be 0,1,2,3 or 4. This is like stating that if you divide any integer by 5, you can only get the remainders 0,1,2,3 or 4.

    Now we test each of those 5 cases in the original proposition. Remember that when we're doing the testing, x does NOT represent a single integer! It represents a whole class of integers (an infinite number) that give that certain remainder when dividing by 5 (loosely speaking). More properly, when we're testing (say) x = 2 (mod 5), we're testing all integers of the form 5k + 2, where k is an arbitrary integer. Each "case" of x that represents an infinite number of integers, is called a congruence class.

    When we test, it may seem like we're acting like we can just substitute that number into the polynomial expression. For example, when we test the case x = 3 (mod 5), we're doing:

    (3^3 + 3^2 + 3^1 + 2) (mod 5) = (27 + 9 + 3 + 2) (mod 5) = 41 (mod 5) = 1(mod 5).

    Remember what I said, x is NOT (necessarily) the actual number 3 here (though one of the values that x can represent is 3). So how are we justified in doing this?

    The answer is that in modulo math, we can multiply and take powers just like we do in normal math. So, if a = b (mod m), we can take nth powers of both sides and get a^n = b^n (mod m). We can also add like in normal math. For example, if a = b (mod m), then a + c = b + c (mod m).

    Those properties (which actually need to be proved in an introductory class to modular arithmetic, but here I'm assuming them as axioms) allow us to just plug in those congruence classes almost like they were just single numbers. But we must be very clear that those are NOT single values of x we're plugging in, even though the calculation is exactly the same.

    So test each of those values of x (mod 5). Which means (for example) writing down: "When x = 0 (mod 5), P(x) = 0^3 + 0^2 + 0 + 2 (mod 5) = 2(mod 5)", etc.

    Once you've tested all 5 possible values of x(mod 5), you've exhausted all the cases.

    You'll see that x = 1 (mod 5) is the ONLY case where P(x) = 0 (mod 5). Which means that P(x) = 0 (mod 5) implies x = 1 (mod 5), and you've proven the proposition you've set out to prove.

    I hope my rather long-winded post has made things much clearer for you.

    Here's something else you may want to do to really SEE what's going on.

    When x = r (mod 5), you know that x = 5k + r, right?

    Try plugging in that value into P(x), i.e. work out P(5k+r). You don't even have to work modulo 5, just work it out in usual arithmetic fashion. Expand out everything using Binomial theorem.

    Now, in that expression, identify which numbers are multiples of 5 and which are not. (Assume for the moment that r is not zero, i.e. that x is not a multiple of 5).

    What happens when you take that expression modulo 5 (i.e. when you divide it by 5 and see what's the remainder)? Remember that all multiples of 5 "vanish" (become zero). What are you left with? Simplify that. Doesn't that just become the polynomial in terms of r, i.e. P(r)?

    This is why if x = r (mod 5), you can just plug that r value into the polynomial like we did. In fact, hamsterman was essentially suggest you use this long method to prove the proposition, which might have been a good idea in hindsight, because it would've helped you to understand what's really going on.
     
    Last edited: Apr 24, 2012
  20. Apr 25, 2012 #19
    Ok thanks for the help, I feel much more confident now!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook