Question

prove that (4n^2+1,144)=1

Answer 1

@ganeshie8

Answer 2

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\)

Answer 3

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

Answer 4

definitely, they are equivalent

Answer 5

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

Answer 6

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

Answer 7

What I mean is by brute force.

Answer 8

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.

Answer 9

Looks good!

Answer 10

Basically he is doing modular arithmetic lol.

Answer 11

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

Answer 12

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\).