Let be a natural power of two. Find the number of numbers equivalent with $ 1 $ modulo $ 3 $ that divide it. Dan Brânzei
Problem
Source: Romanian JBMO TST 2000, day 3, p.2
Tags: number theory, modular arithmetic, algebra
NikoIsLife
16.08.2019 15:22
CatalinBordea wrote: Find the number of numbers $ 1 $ modulo $ 3 $ that divide a natural power of $ 2. $ Dan Brânzei There are infinitely many. Consider all powers of $4$.
CatalinBordea
16.08.2019 15:56
NikoIsLife wrote: CatalinBordea wrote: Find the number of numbers $ 1 $ modulo $ 3 $ that divide a natural power of $ 2. $ Dan Brânzei There are infinitely many. Consider all powers of $4$. No. $ 16 $ does not divide $ 4, $ per example.
NikoIsLife
16.08.2019 16:03
CatalinBordea wrote: NikoIsLife wrote: CatalinBordea wrote: Find the number of numbers $ 1 $ modulo $ 3 $ that divide a natural power of $ 2. $ Dan Brânzei There are infinitely many. Consider all powers of $4$. No. $ 16 $ does not divide $ 4, $ per example. But $16$ divides $32$, which is a power of $2$.
CatalinBordea
16.08.2019 16:07
Ok, my fault. I changed the wording. The answer should depend on the exponent of $ 2. $
NikoIsLife
16.08.2019 16:13
CatalinBordea wrote: Let be a natural power of two. Find the number of numbers equivalent with $ 1 $ modulo $ 3 $ that divide it. Dan Brânzei I assume you mean "Let $2^n$ be a natural power of two."
We know that all the divisors (positive and negative) of $2^n$ are either $1$ mod $3$, or $2$ mod $3$. Otherwise, it would be divisible by $3$, which cannot be a divisor of $2^n$.
Furthermore, if $x$ is a divisor of $2^n$ such that $x\equiv1\pmod3$, then $-x$ is also a divisor of $2^n$, where $-x\equiv2\pmod3$.
Hence, there is a bijection between divisors of $2^n$ that are $1$ mod $3$, and divisors that are $2$ mod $3$.
Since $2^n$ has $2(n+1)$ divisors, this means exactly half of these divisors are $1$ mod $3$. The answer is $\boxed{n+1}$.