1. ## Modulus question

I am currently stuck on a practice problem.

it goes....

Show that if n is an odd integer then...

n^2=1 or 9(mod16)
n^4=1(mod 16)

Show that if n is any integer that is not divisible by 2 or 3, then n^2=1(mod12)

This stuff is so confusing to me :S

2. ## Re: Modulus question

Originally Posted by ehpoc
I am currently stuck on a practice problem.

it goes....

Show that if n is an odd integer then...

n^2=1 or 9(mod16)
n^4=1(mod 16)

Show that if n is any integer that is not divisible by 2 or 3, then n^2=1(mod12)

This stuff is so confusing to me :S
If $\displaystyle \displaystyle n$ is an odd integer, then $\displaystyle \displaystyle n = 2n - 1$.

So $\displaystyle \displaystyle n^2 = (2n - 1)^2 = 4n^2 - 4n + 1 = 4n(n - 1) + 1$.

Notice that $\displaystyle \displaystyle n(n - 1)$ is even, so that means $\displaystyle \displaystyle 4n(n -1 ) = 4(2m) = 8m$

Therefore $\displaystyle \displaystyle n^2 = 8m + 1 = 1\textrm{ or }9 \textrm{ mod }16$.

Also $\displaystyle \displaystyle n^4 = (2n - 1)^4 = 16n^4 - 32n^3 + 24n^2 - 8n + 1 = 8(2n^4 - 4n^3 + 3n^2 - n) + 1 = 8n(n - 1)(2n^2 - 2n + 1) + 1 = 16m(2n^2 - 2n + 1) + 1 = 1 \textrm{ mod }16$

3. ## Re: Modulus question

Thanks so much for the reply!

I don't understand two point of the solution...

n(n-1)....why is this even? is it just by rule?

secondly

I can not readily see how this is true overtly true

8m + 1 = 1 or 9 { mod }16.
EDIT: oh lol I can see why that is true now

4. ## Re: Modulus question

Originally Posted by ehpoc
Thanks so much for the reply!

I don't understand two point of the solution...

n(n-1)....why is this even? is it just by rule?

secondly

I can not readily see how this is true overtly true

8m + 1 = 1 or 9 { mod }16.
EDIT: oh lol I can see why that is true now
If n is even, then n - 1 is odd. The product of an even and an odd is even.

If n is odd, then n - 1 is even. The product of an odd and an even is even.

5. ## Re: Modulus question

I have some upon another problem that is similar so I am just piggybacking it on this thread.

Show that if n is any integer that is not divisible by 2 or 3, then n^2= 1 (mod 12).

6. ## Re: Modulus question

Originally Posted by ehpoc
I have some upon another problem that is similar so I am just piggybacking it on this thread.

Show that if n is any integer that is not divisible by 2 or 3, then n^2= 1 (mod 12).
Hint: $\displaystyle n^2-1=(n-1)(n+1)$

7. ## Re: Modulus question

hint #2: n-1 and n+1 are both even (why?) one of these is divisible by 3 (again, why?)