## anonymous one year ago prove that (4n^2+1,144)=1

1. anonymous

@ganeshie8

2. ganeshie8

Notice that $$144 = 12^2 = 2^43^2$$ $$4n^2+1$$ is always odd, so you just need to show that $$3$$ does not divide $$4n^2+1$$

3. thomas5267

Is $$4n^2+1\not\equiv 0\pmod3$$ equivalent to $$n^2+1\not\equiv 0\pmod3$$?

4. ganeshie8

definitely, they are equivalent

5. ganeshie8

but im not sure if OP has been introduced to congruences..

6. thomas5267

All I can think of no matter $$n\equiv0,1,2\pmod3,\,n^2+1\not\equiv0\pmod3$$.

7. thomas5267

What I mean is by brute force.

8. anonymous

i think we should solve this question using this solution . if n=3k then 4n^2+1 is not divisible by 3. if n=3k+1 then 4n^2+1=4(3k+1)^2+1=4*9k^2+4*6k+4+1=3k'+5 that is not divisible by 3. if n=3k+2 then 4n^2+1=4(3k+2)^2+1=4*9k^2+4*12k+16+1=3k'+17=3k''+2 that is not divisible by 3.

9. ganeshie8

Looks good!

10. thomas5267

Basically he is doing modular arithmetic lol.

11. ganeshie8

Yes, but he thinks that he is using division algorithm... they are essentially same, just the notation is different

12. ganeshie8

By division algorithm, any integer can be expressed uniquely as $$3k+r$$ where $$0\le r\lt 3$$ so it is sufficient to check the $$3$$ cases : $$n=3k,3k+1, 3k+2$$ they cover all the integers, $$n$$.