1

Edit: Find r and n in congruence $827. 3^{839} ≡ r \mod n$

I am new to this modulo arithmetic topic and was given a question to solve.

Find $n$ in the following equation: $$3^{839}\equiv827\bmod n$$

I have tried finding $3^{128}$ and thought of using the power laws to solve this equation but still unable to find $n$.

I am stuck and do not know how to proceed on any further.

sirous
  • 10,751
coffee
  • 61
  • Trivially, you can have $n = 3^{839} - 827$. Without further information, this does not look like a good problem to consider for me. Voting to close. – Jose Arnaldo Bebita Dris Mar 12 '18 at 12:58
  • I took a guess and 1615 seems to work. – Narlin Mar 12 '18 at 13:01
  • @JoseArnaldoBebitaDris You would get a complete answer is you had instead said "$n$ is a divisor of $3^{839}-827$". Considering $827$ is prime and addition / subtraction usually makes factoring difficult, I think trial and error will be the best way to get one answer if that's all you want ($n = 2$ seems to work, for instance). – Arthur Mar 12 '18 at 13:03

1 Answers1

2

839 is prime so using Fermat little theorem we can write:

$3^{839-1}≡1 \mod 839$

Multiplying both sides be 827 we get:

$827\times 3^{838}≡827 \mod 827\times 839≡827\mod 839$

So n can be equal to:

$n=839$ and $839\times 827=693853$

sirous
  • 10,751
  • @coffee, please correct your question to avoid down vote; the correct form of question is: Find r and n in following congruence:$827. 3^{839}≡ r \mod n$ – sirous Mar 12 '18 at 16:10