I haven't learned number theory, and I have encountered a question about it:

Let $p,n,k,m$ be fixed integers such that $p$ a prime, $n$ a positive integer and $k,m$ not divisible by p. We say $x/p^n \equiv y/p^n$ if there exists an integer $z$ such that $x/p^n=y/p^n+z$. Is there must an integer $k'$ such that $k/p^n \equiv mk'/p^n$?

I have tried some numbers and find it holds. However, I don't know much of number theory. I can't make sure it is always right. Thank you for any help.

  • $\begingroup$ (Assuming that $\equiv$ is a mistake and you meant to write $=$) Multiply both sides of the equation by $p^n$, you are asking if there is an integer $k'$ such that $k=mk'$. That is true if and only if $m$ divides $k$ by the very definition of divisibility. There are plenty of choices of $k$ and $m$ such that $m$ does not divide $k$. If this is not what you intended, then please explain what you mean by $\equiv$ instead of $=$ $\endgroup$ – JMoravitz Jul 25 '17 at 1:26
  • $\begingroup$ @ JMoravitz I have explained the meaning of $\equiv$ in my question $\endgroup$ – Xiaosong Peng Jul 25 '17 at 1:36
  • 1
    $\begingroup$ @XiaosongPeng Yes, this is always true. The key is that Euclid's algorithm allows you to find a $k'$ such that $mk'/p^n \equiv 1/p^n$. Then just multiply by $k$ and you can achieve any $k/p^n$. $\endgroup$ – Erick Wong Jul 25 '17 at 1:51
  • $\begingroup$ @JMoravitz As far as I can see, the OP did originally define $\equiv$ to mean equivalence mod $1$, i.e. having the same fractional part. This makes the notation $a/q \equiv b/q$ equivalent to the more standard $a \equiv b \pmod q$. $\endgroup$ – Erick Wong Jul 25 '17 at 1:54
  • 1
    $\begingroup$ Your have posted questions and answers on topics on modules, representation theory, homological algebra, etc. Did you study these topics before elementary number theory? That would be an unusual order.. Are you self-studying? $\endgroup$ – Bill Dubuque Jul 25 '17 at 2:17

Your relation on $x/p^n$ and $y/p^n$ seems to just say that $x$ and $y$ differ by a multiple of $p^n$, that is, if they are equivalent modulo $p^n$.

You're asking if, given $k$ and $m$, you can find a $k^\prime$ such that $k\cong k^\prime m$ modulo $p^n$, given that $k\not\cong 0$ modulo $p^m$.

In more technical language, you're asking if $m$ is a unit in the ring $Z_{p^n}$.

The answer is "yes", since the GCD of $m$ and $p^n$ is 1.

One way to find $k^\prime$ is using Euler's method for finding the GCD of $m$ and $p^n$. For example, if $p^n = 1024$, $m=13$ and $k=9$, you could do this:

  • Divide 1024 by 13, to get the quotient and remainder. Note that $1024=78\times 13 + 10$
  • Divide 13 by 10, to get the quotient and remainder. Note that $13 = 1\times 10 + 3$
  • Divide 10 by 3, to get the quotient and remainder. Note that $10 = 3\times 3 + 1$.
  • Divide 3 by 1, to get the quotient and the remainder. Note that $3 = 3\times 1$ with no remainder.

Then, note this:

  • $1024 = 78\times 13 + 10$, so $10 = 1024 - 78\times 13$.
  • $13 = 1\times 10 + 3$, so $3 = 13 - 1\times 10 = 13 - 1\times(1024 - 78\times 13) = 79\times 13 - 1024$
  • $10 = 3\times 3 + 1$, so $1 = 10 - 3\times 3 = (1024 - 78\times 13) - 3\times(79\times 13 - 1024)$ which equals $4\times 1024 - 315\times 13$

Now you have a formula for $1$ as a multiple of $p^n$ plus a multiple of $m$. You multiple your formula by $k$ to find $k^\prime$:

  • $1 = 4\times 1024 - 315\times 13$, so $9 = 36\times 1024 - 2835\times 13$.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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