Tuesday, October 30, 2018

elementary number theory - Can you show that $3n+1$ is not divisible by $5$ using congruences?



I'm trying to prove that the difference of two consecutive cubes is never divisible by $5$, and I got to a point where I would have to prove that $3n+1$ is not divisible by $5$, where n is an integer. This problem is from a section that deals with congruences and that's why I'd like to know how to show that 3n+1 is not divisible by $5$ using congruences. There might be better ways to solve the actual problem, but for know I'm just interested in the $3n+1$ part.


Answer



$n = 3 \Rightarrow 3n+1 = 10 \equiv 0 \mod 5$. The steps you took to get to this point were not valid.




The difference of two consecutive cubes is $(n+1)^3 - n^3 = 3n^2 + 3n + 1$. A systematic way to check if this is ever divisible by $5$ is to check for $n = 0, 1, 2, 3, 4$. If none of these are, then the quantity is not divisible by $5$ for any integer $n$. Why?



Any integer can be written as $5m + n$ where $n = 0, 1, 2, 3, 4$ and $m \in \mathbb{Z}$. Then $$3(5m+n)^2 + 3(5m+n) + 1 = 3(25m^2 + 10mn + n^2) + 3(5m + n) + 1 \equiv 3n^2 + 3n + 1 \mod 5.$$


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...