# congruence equation

• Aug 31st 2010, 08:55 AM
Danneedshelp
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.
• Aug 31st 2010, 11:53 AM
emakarov
Quote:

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.

Quote:

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.
• Aug 31st 2010, 01:01 PM
Soroban
Hello, Danneedshelp!

Quote:

$\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}
0^3 &=& 0 & \equiv & 0 & \text{mod 6)} \\
1^3 &=& 1 &\equiv & 1 & \text{(mod 6)} \\
2^3 &=& 8 & \equiv & 2 & \text{(mod 6)} \\
3^3 &=& 27 & \equiv & 3 & \text{(mod 6)} \\
4^3 &=& 64 & \equiv & 4 & \text{(mod 6)} \\
5^3 &=& 125 &\equiv& 5 & \text{(mod 6)}
\end{array}$

• Sep 1st 2010, 07:29 AM
Danneedshelp
Quote:

Originally Posted by emakarov

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?
• Sep 1st 2010, 07:33 AM
Danneedshelp
Quote:

Originally Posted by Soroban
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}
0^3 &=& 0 & \equiv & 0 & \text{mod 6)} \\
1^3 &=& 1 &\equiv & 1 & \text{(mod 6)} \\
2^3 &=& 8 & \equiv & 2 & \text{(mod 6)} \\
3^3 &=& 27 & \equiv & 3 & \text{(mod 6)} \\
4^3 &=& 64 & \equiv & 4 & \text{(mod 6)} \\
5^3 &=& 125 &\equiv& 5 & \text{(mod 6)}
\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?
• Sep 1st 2010, 09:42 AM
Isomorphism
Quote:

Originally Posted by Danneedshelp
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.
• Sep 2nd 2010, 03:26 AM
emakarov
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
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
Now, for n=0 and n=1 we see that k=0

Your original problem concerns positive $n$.
Quote:

Originally Posted by Danneedshelp
but 0 is a multiple of any number.

How does this apply?
Quote:

Originally Posted by Danneedshelp
Similarly, if n>2 and odd, then n will at least be divisible by 3

This is not true: consider n=5.
• Sep 2nd 2010, 07:20 AM
melese
Quote:

Originally Posted by Danneedshelp
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.