Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $m, n \in \mathbb{Z}_+$ with $n > 2$, and let $\frac{n^m-1}{n-1}$ be divisible by $17$. Show that either $m$ is even:$ m \equiv 0 \mod 17$ and $n \equiv 1 \mod 17$. Find all possible values of $n$ in the cases when $m$ is even but not divisible by $4$, or divisible by $4$ but not divisible by $8$.

So far, I have done this: First, let's assume that $n \equiv 1 \mod 17$. Also, we know that we can write

$$\frac{n^m-1}{n-1} = \sum_{i = 0}^{m-1} n^i.$$

As $n \equiv 1 \mod 17 \implies n^i \equiv 1 \mod 17$ and so $\sum_{i = 0}^{m-1} n^i \equiv \underbrace{1 + 1 + \cdots + 1} \equiv m$.

Also, we know that $\sum_{i = 0}^{m-1} n^i \equiv 0 \mod 17 \implies m \equiv 0 \mod 17$.

Now, let's assume that $n \not\equiv 1 \mod 17$. Then, $\frac{n^m - 1}{n - 1}$ is divisible by $17$ if $n^m - 1$ is divisible by $17$, i.e $n^m - 1 \equiv 0 \mod 17 \implies n^m \equiv 1 \mod 17$. Fermat's little theorem tells us that $n^{p-1} \equiv 1 \mod p \implies n^{16} \equiv 1 \mod 17$. From here, we have that $m \mid 16$ which tells us that $m$ must be even.

However I am now stuck on the next bit, I'm not sure how to find those values of $n$. Can someone help me please. Thank you.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

You have made considerable progress, indeed you are near the end. If $n\equiv 1\pmod{17}$, then by what you wrote we have $m$ must be divisible by $17$, and any $m$ divisible by $17$ will do. The condition $m$ divisible by $2$ but not by $4$ is easy to meet. We need $m\equiv{34}\pmod{68}$. Then any $n\equiv 1\pmod{17}$ will do the job.

Now let us look at the case $n\not\equiv 1\pmod{17}$. So $n-1$ and $17$ are relatively prime. So our ratio is divisible by $17$ if and only if $n^m\equiv 1\pmod{17}$. This automatically holds if $16$ divides $m$. But our condition on $m$ is that $m$ is divisible by $2$ but not by $4$, so we are far from $16$ divides $m$.

The order of $n$ modulo $17$ divides $16$, so is a power of $2$. We want the order to be exactly $2$. This is the case if and only if $n\equiv -1\pmod{17}$.

For the second part ($m$ divisible by $4$ but not by $8$), there will be some work left to do. You need to determine which $n$ have order $4$ modulo $17$.

share|improve this answer
    
Think you misread it slightly lol, I need the $n$ values, not the $m$ ones. Unless that was a typo on your part? –  Kaish May 24 '13 at 19:40
    
@Kaish: For $m$ of the right shape, any $n$ congruent to $1$ modulo $17$ works. In the material I added, there is a discussion (with proof) of the $n$ that work if $n\not\equiv 1\pmod{17}$. –  André Nicolas May 24 '13 at 19:49

As the first case is perfect, let me start with the second.

As $17$ is prime and hence $\phi(17)=16$

As Primitive Root is a Generator of Reduced Residue System, let's find a primitive root of $17$

$2^4\equiv-1, 2^8\equiv(-1)^2\equiv1\pmod{17} \implies \text{ord}_{17}2=8<\phi(17)$

$3^2\equiv9, 3^4\equiv-4,3^8=(3^4)^2\equiv(-4)^2\equiv-1\pmod {17}$ $\implies \text{ord}_{17}3=16$ i.e., $3$ is a primitive root of $17$

From this, if $d=$ord$_ma,$ ord$_m(a^r)=\frac d{(r,d)}$ where $m,d$ are positive integers and $a,r$ are integers.

So, ord$_{17}(3^n)=\frac{16}{(16,n)}$

Case $1:$ If ord$_{17}(3^n)\equiv2\pmod 4, n=8s$ where $s$ is odd $\implies 3^{8s}=(3^8)^s\equiv(-1)^s\equiv-1\pmod{17}\implies $ord$_{17}(-1)=2$

Case $2:$ If ord$_{17}(3^n)\equiv4\pmod 8, n=4s$ where $s$ is odd $\implies n\equiv4,12\pmod{16}$

Now, $3^4\equiv-4\pmod{17}$ and $3^{12}=3^8\cdot3^4\equiv(-1)(-4)\equiv4\pmod {17}$ $\implies $ord$_{17}(\pm4)=4$

Case $3:$ If ord$_{17}(3^n)\equiv8\pmod {16}, n=2s$ where $s$ is odd $\implies n\equiv2,6,10,14\pmod{16}$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.