3

What is the modular representation of an integer using a set of primes?

More specifically, a problem on my homework asks to convert 49 to a modular representation using primes 7,11,13,17.

Would appreciate a general solution.

James
  • 1,320
  • 1
    Perhaps they're just asking for $49\pmod p$? It certainly doesn't seem like standard terminology to me. – EuYu Oct 14 '12 at 03:04
  • Are you suggesting there are multiple representations of 49, one for each prime? – James Oct 14 '12 at 03:20
  • 1
    Well, yes. It seems like a highly ambiguous problem to me in either case, but $49$ has a representation modulo $p$ for each $p$. So this is certainly one possible interpretation. – EuYu Oct 14 '12 at 03:21
  • Find the remainders when you divide $49$ by the various primes, string them in a row: it is a quadruple that starts with $0, 5$. – André Nicolas Oct 14 '12 at 05:22

2 Answers2

1

Your textbook surely states what they mean by the phrase.

But to take a guess, they're probably referring to a "residue number system", where you represent not-too-large integers as a sequence of residue classes modulo a set of moduli (usually primes).

(to do the reverse conversion, from the residue number system to decimal (or other representations) typically involves the Chinese Remainder Theorem)

  • The thing is, our problem sets have been known to not follow our text's conventions, which is why I wondered if this community could provide some clarification. I have emailed the professor and will update this question. – James Oct 14 '12 at 03:46
0

I saw this in the book, Applied Algebra- Codes, Ciphers and Discrete Logarithms by Darel W.Hardy. It's on page 138 of the second edition, in the section about the Chinese Remainder Theorem and Extended Precision Arithmetic. The accepted answer gives a wonderful summary of the book's content.

In the general case, the author states, "Let $m_1,m_2,...,m_r$" be pairwise relatively prime positive integers with the property that $m_i^2$ can be computed exactly in machine arithmetic. Then any positive integer $n$ less than the product $m_1m_2...m_r$ is determined by the numbers $$ a_1 = n\: mod\:m_1, a_2 = n\: mod\:m_2,...,a_r = n\: mod\:m_r$$ The modular representation of n relative to the bases $m_1,m_2,...,m_r$ takes the form $$ n = [a_1, a_2,...,a_r]$$

Knowing this, we can represent 49 using the primes 7,11,13,17. $$49\:mod\:7 = 0$$ $$49\:mod\:11 = 5$$ $$49\:mod\:13 = 10$$ $$49\:mod\:17 = 15$$ We get $$ 49 = [0, 5,10,15]$$

We can get 49 from its modular representation by solving the system of congruences $$x \equiv 0\;mod\: 7$$ $$x \equiv 5\;mod\: 11$$ $$x \equiv 10\;mod\: 13$$ $$x \equiv 15\;mod\: 17$$

murage kibicho
  • 157