Modular arithmetic (clock arithmetic) is a system of integer arithmetic based on the congruence relation $a \equiv b \pmod{n}$ which means that $n$ divides $b-a$.

learn more… | top users | synonyms

6
votes
3answers
47 views

Modular arithmetic problem (mod $22$)

$$\large29^{2013^{2014}} - 3^{2013^{2014}}\pmod{22}$$ I am practicing for my exam and I can solve almost all problem, but this type of problem is very hard to me. In this case, I have to compute this ...
3
votes
3answers
108 views

Solve the congruence $3x^2+x+8\equiv 0 \pmod{11}$

How to find the solutions of this congruence? $$3x^2+x+8\equiv 0 \pmod{11}$$ I need to find the inverse of $3$, and there I have a problem.
1
vote
0answers
23 views

How to find $y$ given $y^a \equiv b \ mod \ p$ and $a,b,p$?

As I understand it the discrete logarithm problem is about identifying $x$ given $a^x \equiv b \ mod \ p$ and $a,b,p$. While researching this I have become interested in the inverted problem, i.e. ...
1
vote
1answer
38 views

Calculating $n$ mod $m$ given the prime factorization of $n$

Say I have the prime factorization of a large integer $n$. $$n=p_1^{a_{1}}\cdot p_2^{a_{2}}\ldots p_k^{a_{k}}$$ However, I do not have $n$ itself. How do I calculate $n$ mod $m$, given only $n$'s ...
-2
votes
1answer
56 views

Does $x$ have to be finite in $x=0\pmod1$

When we have something like $x=0\pmod1$, the solution for $x$ can be given as $$x=\dots-3,-2,-1,0,1,2,3,\dots$$ I know this goes on infinitely, but is it restricted to finite numbers, making it ...
3
votes
0answers
32 views

Quadratic Residues For Odd Modulo

Say I have the formula $$k^2 \equiv b^2 - 4ac \pmod n$$ where are variables are integers and $n$ is odd. So then my question is, if $b^2-4ac$ and $n$ are constant, when is there never a $k$ that will ...
0
votes
0answers
28 views

Modulus of a 32bit number using 16 bit numbers.

I am trying to calculate the modulo of 2 32bit numbers using 16bit numbers only. a mod b = x if 'a' is greater than a 16 bit I can rewrite the equation as : ...
1
vote
2answers
25 views

How can I apply the Chinese Remainder Theorem when a modulus is the square of another one?

For example: $$\begin{cases} x = 23 \mod 3 \\ x = 8 \mod 9 \\ x = 33 \mod 4 \end{cases}$$ I know that when two moduli are not mutually prime (for example: $$\begin{cases} x = n \mod 45 \\ x = m \mod ...
1
vote
0answers
28 views

Primitive root of unity with certain conditions

Find a primitive $k$-th root of unity $w$ modulo some prime $p$, where $k\geq a$ and $p\geq b$ where $a,b$ are chosen constants. After looking online, I know I can find such values from tables, e.g. ...
1
vote
0answers
30 views

If $\alpha\approx\sqrt p$ and $\beta\approx\log p$, is $\alpha\beta^{-1}\bmod p\approx p$ with probability $1-o(1)$?

Given $p$ a prime and a random $\alpha\in\Bbb Z_p$ with $\alpha\approx\sqrt{p}$ suppose we pick a random $\beta\approx\log p$ then what is the probability that remainder $\alpha\beta^{-1}\bmod p$ is ...
0
votes
1answer
15 views

Diffie-Hellman protocol

So I get the basics of diffie-hellman, discrete logarithms, modular arithmetic etc but I feel like I am missing something substantial or I would not be able to reverse it so easily, unless it is due ...
0
votes
0answers
26 views

Arithmetic complexity of mod powers

Given $a,b,p\in\Bbb N$ what is the computational complexity of computing $a^{p^b}\bmod p$? Is it $O((\log a)(\log b)(\log p))$ arithmetic operations on $\log p$ sized words? $p$ need not be prime.
4
votes
1answer
60 views

Proving that sequence elements satisfy inequality involving $\mod{1}$

I'm trying to prove that $n(3-\sqrt{8}) \; (\!\!\! \mod{1}) < m(3-\sqrt{8}) \; (\!\!\! \mod{1})\;\; \forall \; m < n \;|\;n,m \in \mathbb{N}$ $\leftrightarrow n \in ...
2
votes
0answers
69 views

Solve the congruence relations for x

I have the following two congruence relations: (1) $x^3\equiv 156417\pmod {262063}$ (2) $(7x+19)^3\equiv 6125\pmod {262063}$ And I need to solve this for x. I changed equation (2) into the ...
1
vote
1answer
27 views

What is a supercongruence?

I am very familiar to the congruences in modular arithemtic, But sometimes I can see questions related to supercongruences but I couldn't find any information about it on google. Can someone explain ...
1
vote
3answers
73 views

Prove that every odd prime divides a number of the form $l^2+m^2+1$ $(l,m\in \mathbb {Z})$

I understand this proof http://www.math.uchicago.edu/~may/VIGRE/VIGRE2008/REUPapers/Ng.pdf (Lemma 2.2) until the point "and hence of $-1 - m^2\mod p$ ". Why is this true, and how does the final line ...
2
votes
3answers
85 views

How do you find a multiplicative inverse in modulo arithmetic?

In one of my lectures I have been given this example: When Googling 'multiplicative inverse' most of the tutorials seem to indicate it's as easy as just multiplying a number by the number divided ...
0
votes
1answer
44 views

Given $1010^2=3077^2 \pmod {3551}$ find the factors of $3551$

I am revising for my exams this coming summer and I came across this style of question in my past papers. $1010^2=3077^2 \pmod {3551}$, we are told that $N=3551$ is the product of two prime numbers. ...
1
vote
3answers
51 views

In $a^n \equiv b^n \pmod m$, does $n$ have to be an integer?

In $a^n \equiv b^n \pmod m$, does $n$ have to be an integer? I just came upon this rule and am wondering its limits. Thank you
2
votes
1answer
53 views

Supercongruence for Binomial Coefficients

$${p^{e+1} \choose p\cdot k } \equiv {p^{e} \choose k } \mod p^{e+1} $$ $p$ is prime, $e$ and $k$ are non negative integers. I am struggling with a proof of the above proposition, in the ...
-1
votes
1answer
43 views
0
votes
3answers
48 views

Find $47 n \pmod {41}$ if $n \equiv 13 \pmod {41}$ [closed]

As stated in the title, I'm trying to find $47 n \pmod {41}$ when I know that $n \equiv 13 \pmod {41}$
-4
votes
1answer
33 views

Compute bits per second [closed]

We know a computer can code 1024 bits/sec using a RSA modulus of 1536 bits and the running time of modular exponential with modulus $n$ is $O(\ln^3(n))$. Using a key of 2048 bits, how many bits per ...
2
votes
0answers
52 views

Solve the congruence system

I'm asked to solve the following congruence system: $$ \begin{split} x &\equiv 2 \pmod{5}\\ 2x &\equiv 1 \pmod{7}\\ 3x + y &\equiv 4 \pmod{11} \end{split} $$ But I think that by ...
3
votes
5answers
90 views

What will be the remainder when $2^{31}$ is divided by $5$?

The question is given in the title- Find the remainder when $2^{31}$ is divided by $5$. My friend explained me this way- $2^2$ gives $-1$ remainder. So,any power of $2^2$ will give $-1$ ...
1
vote
5answers
61 views

Let $n ∈ N, n ≥ 1$. Prove that $4^n + 6n - 1$ is divisible by $9$.

I've considered the equation by modulo 9 and tried the binomial theorem $$4^n=(6-2)^n$$ but I still cannot prove it. Maybe there is a clever solution but so far I have been unable to spot it. Can ...
0
votes
1answer
41 views

Order of a prime power modulo a prime power

Suppose that $q = p^n$ where p is a prime. Now assume that $q \equiv 1$ (mod $l$), where $l$ is a different prime, and that $q \not\equiv 1$ (mod $l^2$). How would I find the multiplicative order of ...
0
votes
2answers
29 views

Patterns in Mods of Successive Powers

I was working on a problem for Project Euler and I made an assumption that led to me solving the problem. My assumption was that if we take mods of successive powers with a constant modulo, they will ...
0
votes
0answers
35 views

Is there an efficient way to calculate k so that x^k % m = 1?

I'm toying with modular exponentiation. Not being a mathematician, I could still figure that x^y % m is equivalent to ...
4
votes
1answer
47 views

Existence of Solutions to a $2-$Equation System of Congruences [duplicate]

Do there exist $a, b> 1$, such that $$ a^4 \equiv 1 \pmod{b^2}$$ and $$ b^4 \equiv 1 \pmod{a^2}.$$
17
votes
2answers
138 views

If two integer triples have the same sum of 6th powers, then their sums of squares agree $\bmod 9$

Given $$a^6 + b^6 + c^6 = x^6 + y^6 + z^6$$ prove that $$a^2 + b^2 + c^2 - x^2 - y^2 - z^2 \equiv 0 \bmod{9}$$ I was thinking of using $n^6 \pmod{27}$ and showing both sides have the same pattern ...
1
vote
2answers
45 views

Compute $(235432_7 \cdot 2551_7) \pmod{311_7} = N_7 = ?$

This is for my assembly language class. I am finding different answers. My answer was $15_7$. But a friend got 2824. Can someone please explain the correct way to do it if $15_7$ is wrong? ...
0
votes
6answers
117 views

How is $9^{40}\equiv\ 1 \pmod {100}$?

By Euler's theorem, $a^{\varphi(100)} \equiv\ 1 \pmod {100}$. We know that the last two digits of $9^{40}$ are non-zero. So they can't even be $01$. Since $1\equiv\ 1 \pmod {100}$, how come ...
0
votes
0answers
32 views

Combining solutions of subproblems with CRT when solving discrete logarithm problem with composite modulo

Author of this answer reduces the discrete logarithm problem $a = b^x \pmod{N}$, $N=p q r$, $p,q,r\in {\mathbb P}$ to smaller discrete logarithms problems $a = b^y \pmod{p}$ $a = b^z \pmod{q}$ $a = ...
2
votes
0answers
151 views

Finding a minimal perfect hash function for small sets quickly

I'm trying to solve the computer science problem "Minimal perfect hash function" (MPHF). I have an algorithm that can generate a MPHF for very large sets in $O(n)$ that only needs 1.54 bits/key, very ...
1
vote
5answers
42 views

Exponents and mod (Euler's theorem)

I know how to compute $7^{402} \pmod{10}$ using Euler's theorem since $7$ and $10$ are relatively prime. But is there an easy way without using a calculator to compute $12^{720} \pmod{10}$. I don't ...
3
votes
0answers
19 views

Probability of two correlated numbers modulo p being part of a subset

Let $p$ be a prime number and $x$ be a number chosen uniformly at random from $0,...,p-1$ and let $y=cx \mod p$, where $c$ is some integer in $1,...,p-1$. Let's suppose we chose at random $p/2$ ...
4
votes
2answers
57 views

Last two digits of $2^5+2^{5^2} +\dots +2^{5^{2015}}$

Let $$N=2^5+2^{5^2} +\dots +2^{5^{2015}}.$$ Find the last two digits of $N$. It suffices to find $N \mod 100$. And I observed that $2^{20+n}=2^n\pmod{100}$ for $n \ge 2$. So is the answer just ...
0
votes
0answers
35 views

Congruence for an alternate sum of powers of the odd multiples of a prime

Let $p$ be an odd prime, and $m$ a positive integer, $$S(m,p)=\underset{0\leq k\leq p^{m+1}-1}{\underset{2 k+1\equiv 0 \bmod p}{\Sigma }}(-1)^k (2 k+1)^{m} $$ $S(m,p)$ is an alternate sum of the ...
1
vote
3answers
47 views

Find base of exponentiation

Given the two primes $23$ and $11$, find all integers $\alpha$ such that $\alpha^{11} \equiv 1 \mod 23$. How to compute this? What to use?
0
votes
6answers
57 views

Multiplicative inverse of 47 mod 64.

I have to compute the multiplicative inverse of $47$ $mod 64$. What is the fastest way to do this?
0
votes
2answers
20 views

Clarification regarding multiple modular exponentiation

If the base is same and exponents are different, for e.g. R1=b^x mod p; R2=b^y mod p; R3=b^z mod p; (p is large prime (2048 bit); x, y and z - 160 bit integers)) To calculate R1, R2 and R3 at the same ...
0
votes
1answer
27 views

Modular exponentiation commutativity in Diffie-Hellman

I've been learning about Diffie-Hellman key exchange. One of the main tricks comes down to a commutativity property of exponentiation in the relevant modular arithmetic, it seems. Something like: ...
1
vote
4answers
71 views

If $a ≡ b \pmod 7$, is $a^2 \equiv b^2 (\bmod 7)$?

Let $a$ and $b$ be integers with $a ≡ b \pmod 7$. Is $a^2 ≡ b^2 \pmod 7$? Justify by giving a proof or a counterexample. I actually have no clue how to even begin tackling this question. How ...
0
votes
2answers
17 views

$g$ is a primitive root mod $p$ and $h$ is a primitive root mod $q$. Using CRT find $k$ whose order is exactly lcm$(p-1,q-1)$

Let $q$ and $p$ be unique primes. $g$ is a primitive root mod $p$ and $h$ is a primitive root mod $q$. Using CRT find $k$ whose order is exactly lcm$(p-1,q-1)$ I know that $g^{p-1} \equiv 1 ...
0
votes
0answers
33 views

Subtracting a finite ring

For the finite ring $R_2 = \{00000000,00000001..,11111111\}$ find: $ 11010111 - 10101010 = N_2 =$___________ I am trying to answer this question. I cannot subtract normally in assembly so, using the ...
2
votes
2answers
42 views

Clarification on a Inverse modulo exercise

Find integers $x$ and $y$ such that $49x + 100y = 1$. Which, if either, is the inverse of $49$, modulo $100$? I know the answer to this is $x = 49$ and $y = -24$, but how do I arrive at that? ...
1
vote
2answers
32 views

Congruence arithmetic proof of $2i \equiv 2j \pmod{2m}$ implies $i \equiv j \pmod{2m}$ or $i\equiv j + m \pmod{2m}$.

If $2i \equiv 2j \pmod{2m}$, then either $i \equiv j \pmod{2m}$ or $i + m \equiv j \pmod{2m}$. This is easy to show by using the definition, i.e. if $2m$ divides $2(i-j)$, then either $2m$ divides ...
9
votes
6answers
853 views

Why is $-145 \mod 63 = 44$?

When I enter $-145 \mod 63$ into google and some other calculators, I get $44$. But when I try to calculate it by hand I get that $-145/63$ is $-2$ with a remainder of $-19$. This makes sense to me, ...
26
votes
0answers
349 views

Fractals using just modulo operation

Let us calculate the remainder after division of $27$ by $10$. $27 \equiv 7 \pmod{10}$ We have $7$. So let's calculate the remainder after divison of $27$ by $7$. $ 27 \equiv 6 \pmod{7}$ Ok, so ...