Question

how to show \(n^3-4\) is not divisible by \(13\) for all \(n \in \mathbb{Z}\)

Answer 1

heyy

Answer 2

who???
me ??

Answer 3

green apple

Answer 4

yes sSIR ??

Answer 5

@ganeshie8

Answer 6

*

Answer 7

^^^ what does that mean ??

Answer 8

few observations :

1)
\(n^{12}-4\) is not divisible by \(13\) because \(n^{12}\) leaves a remainder \(1\) or \(0\) by fermat's little theorem

2)
first observation implies \(n^{6}\) has to leave a remainder \(-1\) or \(0\)

Answer 9

is it \[n^3 \] or \[n^{12}\] ??

Answer 10

Ahh our goal is to show n^3 - 4 is not divisible by 13, was just messing with higher powers because they are easy

Answer 11

hmmmm nvm
^_^
srry

Answer 12

One straight forward way is like this :
Every integer can be expressed in one of the forms {13k, 13k+1, 13k+2, ... , 13k+12}

It is sufficient to show that the given statement is true for these 13 cases

Answer 13

case1 : n = 13k
\(n^3 - 4 = (13k)^3 - 4 \equiv -4 \pmod{13}\)
the remainder is -4, so the statement is true for numbers of form 13k

case2 : n = 13k+1
\(n^3 - 4 = (13k+1)^3 - 4 \equiv 1-4\equiv -3 \pmod{13}\)
the remainder is -3, so the statement is true for numbers of form 13k+1

case3 : n = 13k+2
\(n^3 - 4 = (13k+2)^3 - 4 \equiv 8-4\equiv 4 \pmod{13}\)
the remainder is 4, so the statement is true for numbers of form 13k+2

etc...

this works, but im looking for a more neat/compact method

Answer 14

\(\large\tt \begin{align} \color{black}{\hspace{.33em}\\~\\}\end{align}\)

Answer 15

still need help , brb

Answer 16

im looking for an alternative method to prove this w/o using division algorithm

Answer 17

ok using this theorem

Answer 18

\(n^3\equiv 4 \mod 13 \text{ has a solution }\iff 4^{\phi(13)/d} \equiv 1 \mod 13
\\ d=gcd(\phi(13),3)=3\\
\begin{align*}
4^{\phi(13)/3} &=4^{12/3} \\
&= 4^{4}\\
&\equiv 9 \mod 13\not\equiv 1 \mod 13
\end{align*}
\\
\text{thus } n^3\equiv 4\mod 13 \text{ has no solution}
\\
\rightarrow n^3-4\equiv 0\mod 13 \text{ has no solution}\rightarrow
13 \not| n^3-4 \)

Answer 19

\(\text{ some other trick with D.A}\\
n\equiv 0,1,2,3,4,5,6,7,8,9,10,11,12 ~\mod 13\\
n^3\equiv -1,0,1,5,8 ~\mod 13\\
\text{ we need the residues that satisfied }\\

n^3-4 \equiv 0 \mod 13\\
\downarrow \\
\begin{align*}
-1-4 \mod 13 \equiv 8 &\not\equiv 0 \mod 13 \\
0-4 \mod 13 \equiv 9 &\not\equiv 0 \mod 13 \\
1-4 \mod 13 \equiv 10 &\not\equiv 0 \mod 13 \\
5-4 \mod 13 \equiv 1 &\not\equiv 0 \mod 13 \\
8-4 \mod 13 \equiv 4 &\not\equiv 0 \mod 13
\end{align*}
\)

Answer 20

can also simply say
there is no ind 4 mod 13 integer solution ?

Answer 21

\[\large n^3 -4 \ne 0 \mod 13\] We need to prove that this equation is never satisfied, if n is odd, then it won't be satisfied, so we just need to check even values of n. We can represent all numbers as \[\large 13k+m\] with k as any integer and we allow m to vary between 0 and 12 to cover all possible numbers. \[\large 0 \le m \le 12\] But like we said, we don't care about odd numbers, only even numbers so let's multiply 13k+m by 2 and let that be our n: \[\large n = 2(13k+m)=26k+2m\] Now let's just plug it in: \[\large (26k+2m)^3 -4 \equiv 8m^3-4 \mod 13 \\ \large \equiv 4(2m^3-1) \mod 13\]

I guess now I got stuck, I don't really know enough about modular arithmetic to do more with this, I was just thinking that in order for this to work the (2m^3-1) part has to be 13 which means m^3=7 in mod 13 arithmetic, but since they're both coprime then there is no solution, which is what we want. But I'm not really sure if that reasoning works here or not, maybe someone can help.

Answer 22

that looks neat and close to division algorithm argument ! xD

We need to prove that this equation is never satisfied, `if n is odd, then it won't be satisfied, so we just need to check even values of n`. We can represent all numbers as


how do we know odd n's wont work ?

Answer 23

well since odd*odd = odd we know n^3 is odd if n is odd. We also know odd + even = odd so since n^3 is odd, and -4 is even we still have an odd... But now I see a problem... 0 = 13 mod 13 so this argument completely is broken! haha oh well.

Answer 24

but still it proves that there are no solutions in even integers, that part is flawless :)

Answer 25

we are roaming around D.A here as will

Answer 26

Ok here's a new argument, just show that \[\large n^3-4 \ne 0 \mod 13\] and let \[\large n=13k+a \\ \large k \in \mathbb{Z} \\ \large 0 \le a \le 12\] When we plug it in, we have \[\large (13k+a)^3 -4 \ne 0 \\ \large a^3-4 \ne 0 \\ \large a^3 \ne 4\] then we have to somehow show that no cube of any number from 0 to 12 is 4 mod 13. So one way is to just compare the 12 perfect cubes and make sure none of them are 4 larger than a multiple of 13, but that's basically what was said already which is kind of lame.

Answer 27

thats division algorithm and yes it works by exhausting all the 12 cases

Answer 28

its what i did here xD \(\uparrow \)but worked more less

Answer 29

Hahaha sorry I don't know what division algorithm means exactly but I think I kinda get the idea anyways

Answer 30

ok here is an idea
you know according to division algorithm we can all numbers like this :-
\(13k\\
13k+1\\
13k+2\\
13k+3\\
13k+4\\
13k+5\\
13k+6\\
13k+7\\
13k+8\\
13k+9\\
13k+10\\
13k+11\\
13k+12\)

Answer 31

which is the same as
\(13k \equiv 0 \mod 13\\
13k+1\equiv 1 \mod 13\\
13k+2\equiv 2 \mod 13\\
13k+3\equiv 3 \mod 13\\
13k+4\equiv 4 \mod 13\\
13k+5\equiv 5 \mod 13\\
13k+6\equiv 6 \mod 13\\
13k+7\equiv 7 \mod 13\\
13k+9\equiv 9 \mod 13\\
13k+10\equiv 10 \mod 13\\
13k+11\equiv 11 \mod 13\\
13k+12\equiv 12 \mod 13\)

so make ur self free to take mod to power 3,7 or what ever u wont to see at which modulo of 13 it follow