0
votes
3answers
58 views

modules with several powers $x^{y^z}$

I have an assignment(which gives no credit) which I cant solve so I would like to get some help $3^{{1001}^{1002}}\pmod {43}$ (All original numbers were replaced) Our hint was to use the ...
0
votes
0answers
33 views

How to calculate sum of digit of a power

Find the sum of the digits of: $$\left\lfloor\frac{k^{h+1}-1}{h-1}\right\rfloor$$ I need to calculate sum of digits in answer. Note as $k$ and $h$ can be a very big value, answer is getting ...
1
vote
3answers
123 views

How do you calculate a large power modulo a small number? [duplicate]

How do I calculate $12345^{12345} \operatorname{mod} 17$? I cant do it on a calculator? How would I show this systematically?
2
votes
1answer
103 views

Modular exponentiation references

I have recently learned a trick in modular exponentiation that is new to me. By example (as in the linked question/answer above): $$2^{1386}=2^{2^{10}}\cdot 2^{2^8}\cdot 2^{2^6}\cdot 2^{2^5}\cdot ...
2
votes
2answers
46 views

$2^n$ modulo n where n is odd always yields either an even or $1$

I'm attempting to do a pidgeonhole proof to prove that for some odd integer n, there is always a $2^k$ such that $2^k \mod(n) = 1$. I know that $2^n \mod(n)$ will always yield either an even number or ...
1
vote
2answers
45 views

modular exponentiation where exponent is 1 (mod m)

Suppose I know that $ax + by \equiv 1 \pmod{m}$, why would then, for any $0<s<m$ it would hold that $s^{ax} s^{by} \equiv s^{ax+by} \equiv s \pmod{m}$? I do not understand the last step here. ...
1
vote
1answer
24 views

Proof for exponentiation in modular arithemetic

I have found out, that the following is true for modular arithmetic when $t$ is a natural number. $$a^t \bmod\ n \equiv (a\bmod\ n)^t\bmod\ n$$ But I have been unable to find a proof for this, does ...
2
votes
3answers
122 views

Modular Arithmetic with Powers and Large Numbers

I have a question similar to the following: Evaluate $8767^{2123} \mod 15$. So I got $(8767^{11})^{193}$ $(8767^1*8767^{10})^{193}$ $(8767^1*(8767^3 *8767^4))^{193} \mod 15$ Now I haven't ...
4
votes
2answers
231 views

Calculating $a^n\pmod m$ in the general case

It is well known, that $$a^{\phi(m)}\equiv1\pmod m ,$$ if $\gcd(a,m)=1.$ So, $a^n\pmod m$ can be calculated by reducing n modulo $\phi(m)$. But, for the tetration modulo $m$ $$a \uparrow ...
2
votes
0answers
81 views

Fast check If the remainder is 1

Is there any fast method to 'say' that $R = (A \mod B)$ is $1$ or $R > 1$ or $R \neq1$ or $R > k>1$ ( where $k$ is a small integer on $32$ bits) without to actually calculate the real value ...
1
vote
1answer
32 views

Negative powers in modular arithmetic

Suppose we have set $Z = \{0, 1, \dots, N-1\}$ with arithmetic operations modulo $N$; $a > 0$ is an element in $Z$. Is it possible that $a^{-1}$ does not exist but $a^{-n}$ exists for some $n$, $1 ...
0
votes
1answer
35 views

Fractional exponentiation in modular arithmetic

Does raising a modular expression to a fraction mean anything? For example, $a\,\,mod \,\,N$ raised to $1/b$ where $b>0$. Does this violate the rules of modularity?
1
vote
1answer
78 views

Exponentiation by squaring

I need to calculate $7^{2012}$ mod $13$ by hand using exponentiation by squaring, but I cant seem to figure it out. I started with this but I don't know for sure if its correct or where it's going. ...
2
votes
2answers
282 views

How to compute $2^{\text{some huge power}}$

I have to compute $$2^{p-1} \mod p$$ and show by Fermat's little theorem that $p$ isn't prime. I know what the question is asking but I'm not sure how to reduce the exponent on $2^{p-1}$ to a more ...
-1
votes
1answer
92 views

Is $2^n \mod m \equiv (2^{n/2} \pmod m ) ^ 2 \pmod m$?

I'm trying to write a procedure that solves (2^n - 1) mod 1000000007 for a given n. n can ...
0
votes
1answer
43 views

Modular Exponentiation Equivalence Problem

Find the integer $a$ such that $0 \leq a < 113$ and $102^{70} + 1 \equiv a^{37} \bmod{113}$. I started off by using modular exponentiation to realize that the left side of the congruence is ...
2
votes
3answers
62 views

computing $2^{170}+ 3^{63}\pmod {19}, 3^{175} + 2^{73} \pmod {17}$, etc… by hand

I came across several questions like this in the problem section of a book on coding theory & cryptography and I have no idea how to tackle them. There must be a certain trick that allows for ...
2
votes
1answer
70 views

Modulo operation of large powers

I came through this property in a cryptography book. $(ab)\bmod n=\bigl((a \bmod n)(b \bmod n)\bigr)\bmod n$. There is an example in the book, $10^n\bmod 3= (10\bmod n)^n$. Now if I have ...
0
votes
1answer
266 views

RSA and calculating huge exponents

I am writing an Extended Essay on RSA encryption and in the essay, I am going through a worked example of all of the stages involved (key generation, encrypting and decrypting). I am using very small ...
1
vote
1answer
65 views

$(A^x) \mathbin\% p = (A^{x \mathbin\% (p - 1)}) % p$ if $p$ is prime. Is this true when $A$ is a matrix?

$(A^x) \mathbin\% p = (A^{x \mathbin\% (p - 1)}) % p$ if $p$ is prime. Is this property true when $A$ is a matrix? Suppose $$A=\begin{pmatrix} 1 &0 &1\\ 1 &0 &0\\ 0 &1 &0 ...
2
votes
2answers
74 views

Large exponential modular

Proof $2011^{2011^{2011}}-2011 \equiv 0 \mod 30030$ By Chinese Remainder Theorem this is equivalent to proving: $2011^{2011^{2011}}-2011 \equiv 0 \mod 2$ $2011^{2011^{2011}}-2011 \equiv 0 \mod 3$ ...
2
votes
1answer
69 views

Why inverse modulo exponentiation is harder than inverse exponentiation without modulo

I am new to number theory. I read in cryptography inverse modulo exponentiation is used because it is hard. But I couldn't understand the advantage of it over inverse exponentiation without modulo. ...
0
votes
1answer
66 views

Does $ \ (g^a Mod\ p)^b\, $ $\equiv$ $ \ (g^a)^b (Mod\ p)\, $ hold true?

Are these two equations: $$ \ (g^a Mod\ p)^b\, $$ $$ \ (g^a)^b (Mod\ p)\, $$ one and the same? If yes then how And if no then how to solve the first equation?
-1
votes
3answers
141 views

Find the smallest natural number that satisfy $13^N = 1 \pmod {2013}$

Moderator Note: This is a current contest question on Brilliant.org. Find the smallest natural number that satisfy: $$13^N = 1 \pmod {2013}$$ My idea is to use the Fermat's little theorem ...
9
votes
7answers
2k views

Pattern to last three digits of power of $3$?

I'm wondering if there is a pattern to the last three digits of a a power of $3$? I need to find out the last three digits of $3^{27}$, without a calculator. I've tried to find a pattern but can not ...
2
votes
4answers
108 views

If $3^x \bmod 7 = 5$, what is $x$ and how?

I am an amateur java programmer who is stuck on this problem: $$3^x \bmod 7 = 5$$ then what is $x$ and how? If you can even explain the method for how to arrive at the solution, then it will be very ...
2
votes
3answers
113 views

How to find this expression $1000! \mod 3^{300}$

How to find this expression $(1000!\mod 3^{300})$?
3
votes
2answers
90 views

Is there an easy way to find $2^p \pmod p$?

I'm working on a number theory problem, and was able to simplify an expression down to a quadradic in $2^p \pmod p$? Is there an easy way to compute that, or must I work it out in $O(p)$ complexity?
2
votes
1answer
112 views

How to build fast exponentation for modular?

I need to find modular value of some big number which I cannot calculate by calculator (i.e $233^{351} \pmod {853}$. How can I build a fast exponentiation table for this?
0
votes
1answer
162 views

Modular arithmetic: mod p-1 after exponentiation?

I keep coming across proofs that seem to use the following derivation, but I'm unsure where it comes from. What theorem shows that this is a correct step to take? $ g^{x} = g^y$ mod $p$ $\iff$ $x = ...
2
votes
2answers
81 views

Proving that $x^a=x^{a\,\bmod\,{\phi(m)}} \pmod m$

i want to prove $x^a \equiv x^{a\,\bmod\,8} \pmod{15}$.....(1) my logic: here, since $\mathrm{gcd}(x,15)=1$, and $15$ has prime factors $3$ and $5$ (given) we can apply Euler's theorem. we know that ...
0
votes
2answers
73 views

Computing $\left\lfloor\sum_{k = 1}^{n}{\varphi^{3k}}\right\rfloor$

I'm trying to find $\left\lfloor\sum_{k = 1}^{n}{\varphi^{3k}}\right\rfloor$ mod $m$. $\varphi = \frac{1 + \sqrt{5}}{2}$ and $\varphi^3 = 2 + \sqrt{5}$. But honestly I'm not even sure where to start. ...
6
votes
5answers
7k views

How do you calculate the modulo of a high-raised number?

I need some help with this problem: $$439^{233} \mod 713$$ I can't calculate $439^{223}$ since it's a very big number, there must be a way to do this. Thanks.
1
vote
1answer
570 views

Modulo of (Power of 2 divided by a number)

I wanted to calculate the power of $2$ raised to a number $a$, divided by another number $b$ and then take the modulo $K$ of this quantity. Meaning, I basically wanted $(2^a/b) \mod K$. Take an ...
3
votes
1answer
376 views

Calculating the residue of power towers

I want to calculate the residue of a power tower. How do I do that? For example, I want to know the answer to this: $$2 \uparrow\uparrow 10 \pmod{10^9}$$
2
votes
0answers
115 views

Determining maximum value of $a^b\bmod N$ when $\gcd(a,b)$ is known

Suppose we know the greatest common divisor, $\gcd(A,B)$, of two numbers $A$ and $B$. Is there a way that we can find the maximum value of $a^b \bmod N$ where $N$ is any number? We have a finite ...
1
vote
0answers
102 views

Collaborative modular exponentiation

EDIT: Rephrased. I have, stored somewhere, the values $a$ , $Q$, $N_1$ (plus its factor) and $a^{2Q} \mod N_1$. I also know $b$, $R$ and $N_2$ (but not its factors). I want to know whether there is ...
1
vote
3answers
870 views

Modular exponentiation?

I came upon an interesting way to relatively quickly compute modular exponentiation with large numbers. However, I do not fully understand it and was hoping for a better explanation. The method ...
4
votes
3answers
150 views

Calculate $11^{35} \pmod{71}$

Calculate $11^{35} \pmod{71}$ I have: $= (11^5)^7 \pmod{71}$ $=23^7 \pmod{71}$ And I'm not really sure what to do from this point..
4
votes
3answers
833 views

Calculating $17^{14}\mod{71}$ using Fermat's little theorem

Calculate $17^{14} \pmod{71}$ By Fermat's little theorem: $17^{70} \equiv 1 \pmod{71}$ $17^{14} \equiv 17^{(70\cdot\frac{14}{70})}\pmod{71}$ And then I don't really know what to do from this point ...
4
votes
5answers
285 views

What is the remainder of $(14^{2010}+1) \div 6$?

What is the remainder of $(14^{2010}+1) \div 6$? Someone showed me a way to do this by finding a pattern, i.e.: $14^1\div6$ has remainder 2 $14^2\div6$ has remainder 4 $14^3\div6$ has remainder 2 ...
2
votes
1answer
106 views

Is it possible to know if sums of powers of a number is divisible by another number?

Is there a way to find whether a number (say $A$) formed by summing powers of another number (say $B$) is divisible by another number $C$? $A$ is a number like, for example, $B^1+B^3$. We can use a ...
2
votes
1answer
128 views

how to minimize y in expression $(x^y) \bmod{n}$?

Let's consider $x^y\bmod{n}$. $y$ comparing to $x$ and $n$ is veeeeeeeery big. How can we minimize $y$ such that $(x^{\mathrm{newy}}) \bmod{n}$ gives same result as $(x^y) \bmod{n}$? What are the ...
2
votes
4answers
7k views

Modulo arithmetic with big numbers?

I need to calculate $3781^{23947} \pmod{31847}$. Does anyone know how to do it? I can't do it with regular calculators since the numbers are too big. Is there any other easy solutions? Thanks
2
votes
1answer
303 views