Results 1 to 8 of 8

Math Help - congruence equation

  1. #1
    Senior Member Danneedshelp's Avatar
    Joined
    Apr 2009
    Posts
    303

    congruence equation

    Q1:

    Prove or disprove: for every positive integer n, the congruence equation n^{3}=n(mod6) must hold.

    Q2:

    Prove or disprove: if n is an integer greater than 2, n^{5}-1 is composite.

    Here are my thoughts:

    A1: Let n be any positive integer. Suppose n^{3}=n(mod6) does not hold. Thus, it is not the case that 6|n^{3}-n. Now, notice that n^{3}-n=n(n^{2}-1). We can see that n^{2}-1 is even whenever n is odd and vice-versa. Hence, either expression will at least be divisible by two, which is a factor of 6. Thus, 6|n(n^{2}-1) which is the same as 6|n^{3}-n. This contradicts our original claim.

    I don't know much about modular arithmetic, so I am not sure if I am doing this right.

    A2: Again, I begin a proof by contradiction. Although, I am not sure if it is true or not. I have tested some numbers and it seems to hold. I am having trouble finding a good starting point. There is not much infromation.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    A1: Let n be any positive integer. Suppose does not hold. Thus, it is not the case that . Now, notice that . We can see that is even whenever is odd and vice-versa. Hence, either expression will at least be divisible by two, which is a factor of 6. Thus, which is the same as . This contradicts our original claim.
    First, a remark about the shape of the proof. You are proving some statement A (in this case, it is n^3\equiv n\pmod{6} where n is a positive integer). One can assume \neg A, then prove A and thus obtain a contradiction with the assumption. Therefore, \neg A is false and A is true. However, proof by contradiction is superfluous in your reasoning because in proving A (the first time) you don't use the assumption \neg A. To put it simply, you prove A directly, so why do you need \neg A at all?

    Next, you are right that one of n and n^2-1 is even, so n(n^2-1) is also even. However, it does not follow from there that 6\mid n(n^2-1). For example, 4 is even, but 6 does not divide 4. You should factor n^2-1 further and conclude that one of the three factors of n^3-n is divisible by 3.

    Prove or disprove: if is an integer greater than 2, is composite.
    By Bézout's theorem, n^5-1 is divisible by n-1. You don't need to understand the proof; it is enough to perform the factorization.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,738
    Thanks
    644
    Hello, Danneedshelp!

    \text{Prove or disprove: for every positive integer }n,

    . . \text{the congruence }n^3\:\equiv\:n\text{ (mod 6)}\,\text{ must hold.}

    How about a very primitive proof?


    All positive integers are congruent to 0, 1, 2, 3, 4, or 5 (mod 6).
    . . So we need to test only these six values.

    . . . . . \begin{array}{cccccc}<br />
0^3 &=& 0 & \equiv & 0 & \text{mod 6)} \\<br />
1^3 &=& 1 &\equiv & 1 & \text{(mod 6)} \\<br />
2^3 &=& 8 & \equiv & 2 & \text{(mod 6)} \\<br />
3^3 &=& 27 & \equiv & 3 & \text{(mod 6)} \\<br />
4^3 &=& 64 & \equiv & 4 & \text{(mod 6)} \\<br />
5^3 &=& 125 &\equiv& 5 & \text{(mod 6)} <br />
\end{array}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Danneedshelp's Avatar
    Joined
    Apr 2009
    Posts
    303
    Quote Originally Posted by emakarov View Post

    Next, you are right that one of n and n^2-1 is even, so n(n^2-1) is also even. However, it does not follow from there that 6\mid n(n^2-1). For example, 4 is even, but 6 does not divide 4. You should factor n^2-1 further and conclude that one of the three factors of n^3-n is divisible by 3.
    So, if I further factore I have that n^{3}-n=n(n^{2}-1)=n(n-1)(n+1). Now, if 6|n(n-1)(n+1), then there exists a K such that \frac{n(n-1)(n+1)}{6}=k. Now, for n=0 and n=1 we see that k=0, but 0 is a multiple of any number. Furthermore, for any n>1, at least one of (n+1) or (n-1) will be divisible by 3 whenever n is even. Similarly, if n>2 and odd, then n will at least be divisible by 3 and (n+1) or (n-1) will be divisible by 2. Since 6=2*3, we have show that 6|n^{3}-n, because n^{3}-n=n(n+1)(n-1).

    Does that look better?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member Danneedshelp's Avatar
    Joined
    Apr 2009
    Posts
    303
    Quote Originally Posted by Soroban View Post
    Hello, Danneedshelp!


    How about a very primitive proof?


    All positive integers are congruent to 0, 1, 2, 3, 4, or 5 (mod 6).
    . . So we need to test only these six values.

    . . . . . \begin{array}{cccccc}<br />
0^3 &=& 0 & \equiv & 0 & \text{mod 6)} \\<br />
1^3 &=& 1 &\equiv & 1 & \text{(mod 6)} \\<br />
2^3 &=& 8 & \equiv & 2 & \text{(mod 6)} \\<br />
3^3 &=& 27 & \equiv & 3 & \text{(mod 6)} \\<br />
4^3 &=& 64 & \equiv & 4 & \text{(mod 6)} \\<br />
5^3 &=& 125 &\equiv& 5 & \text{(mod 6)} <br />
\end{array}
    Why do I need to only check the six? Does this mean, if I had some congruence eqaution in mod 13, I would only have to test values from 0 to 12?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Danneedshelp View Post
    Q1:

    Prove or disprove: for every positive integer n, the congruence equation n^{3}=n(mod6) must hold.

    Here are my thoughts:

    A1: Let n be any positive integer. Suppose n^{3}=n(mod6) does not hold. Thus, it is not the case that 6|n^{3}-n. Now, notice that n^{3}-n=n(n^{2}-1). We can see that n^{2}-1 is even whenever n is odd and vice-versa. Hence, either expression will at least be divisible by two, which is a factor of 6. Thus, 6|n(n^{2}-1) which is the same as 6|n^{3}-n. This contradicts our original claim.

    I don't know much about modular arithmetic, so I am not sure if I am doing this right.
    Soroban has done this for you.

    It suffices to look at {0,1,2,3,4,5} because every positive number is congruent modulo 6 to one of the elements of {0,1,2,3,4,5}. And this statement follows from the fact that these are the only remainders possible when you divide a number by 6.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    I agree: the idea to consider the first six numbers is nice.

    Concerning the other idea, here is some critique.

    Quote Originally Posted by Danneedshelp View Post
    So, if I further factore I have that n^{3}-n=n(n^{2}-1)=n(n-1)(n+1). Now, if 6|n(n-1)(n+1), then there exists a K such that \frac{n(n-1)(n+1)}{6}=k.
    It raises a red flag immediately if you say "If" followed by the claim you need to prove. When you are asked to prove A, it's like you are asked to pay the price of A, whereas when you assume A to prove B, it's like asking someone to give you the price of A so that you can buy B. When you go to the grocerie to buy milk, you don't say to the cashier, "Please, give me enough cash to buy milk"; it's you who has to give cash.

    What you probably mean here is, " 6\mid n(n-1)(n+1) is equivalent to the fact that there exists a k such that \frac{n(n-1)(n+1)}{6}=k, so it is enough to show the latter". Note that you in fact use right-to-left implication: "if there exists a k such that \frac{n(n-1)(n+1)}{6}=k, then 6\mid n(n-1)(n+1)". Of course, when both things mean the same by definition, it seems like nitpicking, but still.

    Quote Originally Posted by Danneedshelp View Post
    Now, for n=0 and n=1 we see that k=0
    Your original problem concerns positive n.
    Quote Originally Posted by Danneedshelp View Post
    but 0 is a multiple of any number.
    How does this apply?
    Quote Originally Posted by Danneedshelp View Post
    Similarly, if n>2 and odd, then n will at least be divisible by 3
    This is not true: consider n=5.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by Danneedshelp View Post
    So, if I further factore I have that n^{3}-n=n(n^{2}-1)=n(n-1)(n+1). Now, if 6|n(n-1)(n+1), then there exists a K such that \frac{n(n-1)(n+1)}{6}=k. Now, for n=0 and n=1 we see that k=0, but 0 is a multiple of any number. Furthermore, for any n>1, at least one of (n+1) or (n-1) will be divisible by 3 whenever n is even. Similarly, if n>2 and odd, then n will at least be divisible by 3 and (n+1) or (n-1) will be divisible by 2. Since 6=2*3, we have show that 6|n^{3}-n, because n^{3}-n=n(n+1)(n-1).

    Does that look better?
    Maybe using the Division Algorithm will help you with a way to simpilfy cases for n . By this theorem, any integer n has exactly one of the following forms: 3q, 3q+1, and 3q+2.

    Now, factorize n^3-n=n(n^2-1)=(n-1)n(n+1) and note that we have a product of three consecutive integers; by examination of cases on n you can see that n-1 , n , or n+1 is divisible by 3. For example, suppose n=3q+1, then (n-1)n(n+1)=3q\cdot(3q+1)\cdot(3q+2) so the product is divisible by 3. Check! for the other two cases, namely, n=3q and n=3q+2 . This shows that n^3-n is divisible by 3.

    n^3-n is also divisible by 2, and since 2 and 3 are relatively prime it follows that n^3-n is divisible by 6.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 18th 2010, 06:26 AM
  2. 2^x in a congruence equation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 15th 2009, 05:08 PM
  3. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 28th 2008, 05:54 PM
  4. Congruence Equation
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 13th 2006, 05:00 PM
  5. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 15th 2006, 07:10 PM

Search Tags


/mathhelpforum @mathhelpforum