If I know value of $a$ and also it is known that $$a \equiv 1 \pmod n$$ how can I calculate value of $n$?
Asked
Active
Viewed 3,139 times
2
-
3$n$ can be any divisor of $a-1$ – lab bhattacharjee Apr 14 '14 at 18:31
-
@labbhattacharjee Thanks for your answear. But can you explain why this dependency holds? – Rop Apr 14 '14 at 18:37
-
1that's how Congruence is defined : http://mathworld.wolfram.com/Congruence.html – lab bhattacharjee Apr 14 '14 at 18:40
2 Answers
3
To explain the comment above:
$$a = 1 \mod n$$ $$\iff a = 1 + k \cdot n$$ $$\iff a - 1 = k \cdot n$$ $$\iff n = \frac{a-1}{k}$$
... and $n$ should be an integer, shouldn't it?
chaosflaws
- 274
-
Though, there is nothing wrong with n not being an integer, but to retain a meaningful relationship, k must be an integer. "There exists an integer k such that nk = a - 1" is a more appropriate thing to say. – Jonathan Hebert Apr 14 '14 at 19:19
-
-
"a is congruent to b (mod n) iff there exists an integer k such that a = kn + b" does not require that n be an integer at all (nor a and b). It is only when you require integers that you get statements about divisibility. You may ask why it would ever be useful to take a noninteger as the modulus, but you don't need to look far. As a quick example, if real a and b are congruent (mod 2π), their cosines are equal. – Jonathan Hebert Apr 14 '14 at 19:35
-
And if you want mod 0 to remain undefined, requires that k be unique. I personally see no reason to do that, but just to mention. – Jonathan Hebert Apr 14 '14 at 19:42
-
2
Take for example, $15 = 27$ $mod$ $4$. What this basically means is that $15$ and $27$ both leave the same remainder when divided by $4$, that is 3. In that sense they are equal. They also leave the same remainder $1$ when divided by $2$, so therefore $15=27$ $mod$ $2$. Can you figure out now the relation between $a$ and $n$?
The very fluffy Panda
- 2,284