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.

I'm currently working through Stewart and Tall's Algebraic Number Theory. In particular, section 4.9 of this book provides a proof of the Ramanujan-Nagell Theorem, which states that the only integer solutions of the equation $x^2 + 7 = 2^n$ in integers $x$ and $n$ are given by $$\begin{align} x &= \pm 1, & n &= 3,\\[0.05in] x &= \pm 3, & n &= 4,\\[0.05in] x &= \pm 5, & n &= 5,\\[0.05in] x &= \pm 11, & n &= 7,\\[0.05in] x &= \pm 181, & n &= 15.\\[0.05in] \end{align}$$

The proof is given nearly verbatim in this pdf starting on page 6.

Towards the end of the proof, we find that the solutions of the the congruence $$-2^{m-1} \equiv m \pmod{7}$$ are $m = 3$, $5$, or $13 \pmod{42}$ ($m$ is assumed to be odd), and then aim to show that only $3$, $5$ or $13$ can occur. We let $m_1$ and $m$ be two such solutions that are congruent modulo $42$ and let $l$ be such that $7^l$ is the largest power of $7$ dividing $m-m_1$.

The part of the proof that confuses me follows after this. It is stated that

$$(1+\sqrt{-7})^{m_1 - m} \equiv 1 + (m_1 - m)\sqrt{-7} \pmod {7^{l+1}}$$

and that this follows by

first, [raising] to powers $7, 7^2, \ldots, 7^l$, then $\frac{(m - m_1)}{7^{l}}$.

What are we raising to the powers $7,\ldots,7^l$, and how does the congruence follow from this? I really do not understand this congruence; I had initially assumed that it was assumed $m_1 < m$ because directly above this congruence we raise $1/2$ to the power $m_1 - m$, so if $m_1 - m$ were negative this would just be $2^{m-m_1}$. I've not seen congruences with fractions before, but I would otherwise assume that $1/2$ is congruent to $4$ modulo $7$, being the inverse of $2$ in $\mathbb{Z}_7^*$.

I would assume that the answer to how this congruence is solved would also help me to understand why

$$a^m \equiv \frac{1 + m\sqrt{-7}}{2^m} \pmod{7}$$ where $$a = \frac{1 + \sqrt{-7}}{2}$$

because in both cases the exponent of one side somehow ends up as a multiplicative factor on the other.

To try and understand why these congruence relations hold, I picked up Introduction to Number Theory by James E. Shockley, but the only thing I've found that involves handling powers in congruence relations is indices; I feel this is not relevant because I don't see how primitive roots come into play here, but I admit my understanding of this is limited.

Finally, we then substitute the congruence relation given for $a^m$ into a congruence modulo $7^{l+1}$. This confuses me because the congruence relation with $a^m$ is given modulo $7$ - how can we substitute congruences when one is given modulo $7$ and the other modulo $7^{l+1}$? i.e. if $\gamma \equiv 0 \pmod{7}$ it won't be necessarily true that $\gamma \equiv 0\pmod{49}$ as $\gamma$ could have been $14$, etc.

I would appreciate any help in understanding this. If I've completely missed some fact about congruences or whatnot, if you could suggest textbooks that would be good for understanding them better that would be great too! Thanks.

PS. I'm new to the site, so if there was anything done poorly or incorrectly with posting this question please let me know, i.e. formatting, question too long and rambling, etc.

share|improve this question
2  
If you prefer to write congruences like $$a\equiv b\pmod{n},$$ then the right command would be \pmod{n} at the end. I fixed up a few other formatting issues. You can see here how I edited your post, and you can see here and here for advice with MathJax and Markdown, respectively. –  Zev Chonoles Jul 6 '13 at 18:45
    
Thanks for the edits! I'll be sure to try and follow the formatting as given in the links you've provided henceforth. –  Garnet Jul 6 '13 at 19:00

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.