Residues

For students of class 11-12 (age 16+)
Zan
Posts: 16
Joined: Fri Jun 08, 2012 8:26 pm

Residues

Unread post by Zan » Fri Jun 22, 2012 1:22 am

Find all $n\in\mathbb{N}$ so that all residues modulo $n$ can be written in the form $\frac{m(m+1)}{2}$ mod $n$ with $m\in\mathbb{N}_0$.

User avatar
Phlembac Adib Hasan
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

Re: Residues

Unread post by Phlembac Adib Hasan » Sun Jun 24, 2012 6:11 pm

Nice problem, Zan.Post more and more like these. :D
Attachments
Residues.pdf
I had to type it very swiftly.Please inform me if anybody can identify a typo.
(37.72 KiB) Downloaded 196 times
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Zan
Posts: 16
Joined: Fri Jun 08, 2012 8:26 pm

Re: Residues

Unread post by Zan » Sun Jun 24, 2012 11:01 pm

Phlembac Adib Hasan wrote:So $f(i)\not\equiv0$(mod $n$) if $i\in N_n-0 \ldots$
Could you explain it, please? And did you mean $i\in N_n \backslash0$?

User avatar
Phlembac Adib Hasan
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

Re: Residues

Unread post by Phlembac Adib Hasan » Mon Jun 25, 2012 8:40 am

Zan wrote:
Phlembac Adib Hasan wrote:So $f(i)\not\equiv0$(mod $n$) if $i\in N_n-0 \ldots$
Could you explain it, please? And did you mean $i\in N_n \backslash0$?
Yes.Also $N_{2^k}\equiv N_{2^{k+1}}-N_{2^k}(mod\; 2^k)$ means $N_{2^k}\equiv N_{2^{k+1}}\backslash N_{2^k}(mod\; 2^k)$
Like I said before, I was in a hurry and I avoided typing long codes like \backslash.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Zan
Posts: 16
Joined: Fri Jun 08, 2012 8:26 pm

Re: Residues

Unread post by Zan » Mon Jun 25, 2012 1:11 pm

Thanks!
But could you explain me your argumentation, please?
I'm not very fast ;)

User avatar
Phlembac Adib Hasan
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

Re: Residues

Unread post by Phlembac Adib Hasan » Mon Jun 25, 2012 6:36 pm

Which part?
At first I showed we need to find those $n$s for which $S_n=\{\frac {0\cdot 1}{2},\frac {1.2}{2},...,\frac {(n-1)n}{2}\}$ form a complete residue system modulo $n$.Hence there must be only one element in the set which is divisible by $n$.As we are seeing $n|\frac {0\cdot 1}{2}$, so no other element in $S_n$ is divisible by $n$.Then I showed $n$ can't be odd because $n|\frac {(n-1)n}{2}$, another element of $S_n$ if $n$ is odd.Next I showed If $n=2^aq$($q$ odd>1), then we can find another element in $S_n$,different from $\frac {0\cdot 1}{2}$, which is divisible by $n$.(For example, if $n=12$ then $12|\frac {8\times 9}{2}$.)At last I proved by induction that each positive integer power of $2$ satisfies the conditions.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Zan
Posts: 16
Joined: Fri Jun 08, 2012 8:26 pm

Re: Residues

Unread post by Zan » Mon Jun 25, 2012 6:51 pm

The part (i) with a lot of dots.

User avatar
Phlembac Adib Hasan
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

Re: Residues

Unread post by Phlembac Adib Hasan » Mon Jun 25, 2012 7:12 pm

I hate formal solution writing because it makes everything crazy. :x Notice that for each $i\in N_n$,\[i\equiv f(b_{n_{i}})(mod\; n).\]So $\{f\left (b_{n_{0}}\right ),f\left (b_{n_{1}}\right ),...,f\left (b_{n_{n-1}}\right )\}$ makes complete residue set modulo $n$.Notice that all $b_{n_{i}}$s must be distinct modulo $n$ to follow the last condition.So for each $b_{n_{i}}$ there exists a unique $a_{n_{b_{n_{i}}}}\in N_n$ from the first definition.Hence it follows that \[f\left (b_{n_{i}}\right )\equiv f\left (a_{n_{b_{n_{i}}}}\right )(mod\; n)\].So it follows that $S_n$ is reduced residue system modulo $n$.Last part of $(i)$ is explained in my previous post.Let me know whehter it is clear enough now.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Zan
Posts: 16
Joined: Fri Jun 08, 2012 8:26 pm

Re: Residues

Unread post by Zan » Mon Jun 25, 2012 7:31 pm

Thank you very much!

sourav das
Posts: 461
Joined: Wed Dec 15, 2010 10:05 am
Location: Dhaka
Contact:

Re: Residues

Unread post by sourav das » Tue Jun 26, 2012 8:20 pm

I want to give another solution:
Actually given condition implies that we need to find those $n$ such that set $A=\{x|x=\frac{m(m+1)}{2}$ and $m\in \mathbb N_0$ and $0\leq m \leq n-1\}$ is a complete residue set modulo $n$.

We claim all $n=2^k$ works where $k\in \mathbb N_0$
First let us prove $n>1$ odd won't work
Proof:
It's simple as for $m=0,n-1$ , both are congruent to $0$ mod $n$ as $n$ odd

It implies $n$ cannot have any odd prime factor.
--------
Now , for the contrary of our claim let there exist $n,m$ non- congruent mod $2^k$ such that $\frac{n(n+1)}{2}=\frac{m(m+1)}{2}$ $(mod 2^k) $,Implies $\frac{(m-n)(m+n+1)}{2}=0$ ($mod$ $2^k$) .as only one of $\frac{m-n}{2},\frac{m+n+1}{2}$ is even. It implies $2^k|\frac{m+n+1}{2}<2^k$ So, contradiction. (Proved)
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

Post Reply