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

1
vote
2answers
25 views

How to calculate $x$ in $19^{93}\equiv x\pmod {162}$?

I have to calculate $19^{93}\equiv x\pmod {162}$. All I can do is this,by using Euler's Theorem:- $19^{\phi(162)}\equiv1\pmod{162}$ So,$19^{54}\equiv1\pmod{162}$ Now,I have no idea how to reach ...
0
votes
1answer
39 views

Number of $x^3$ required to equal $2002^{2002}$.

While working on math problems, I came upon a high-power summing problem, and got bogged down. The problem is as follows: What is the smallest positive integer $t$ such that there exist integers ...
2
votes
1answer
29 views

$a^{100}-1$ is divisible by $1000$.

While working on competition math, I came upon the following problem: How many integers $x$ from $1$ to $1000$ are there such that $x^{100}-1$ is divisible by $1000$? This was very confusing, as the ...
5
votes
0answers
33 views

Is there a clever way to find a smaller number that produces the Euclidean algorithm of given length?

Is there a simple way to tell if for a given $n$ there is $m$ such that the Euclidean algorithm on $n,m$ runs for a given number of steps, and/or a way to find $m$ efficiently (other than testing all ...
0
votes
1answer
7 views

Time complexity of modulo scenario

Something theoretical here. Say if I have two natural numbers $x$ and $y$. Both these numbers are upper-bounded by a third number $z$. ($O$($z$)) Now let's say I have a recursive modulo function ...
-2
votes
1answer
53 views

Do the $2$ modulus $3$ can be $-1$ or just $2$?

I need to calculate $2$ modulus $3$ as $2<3$ then the answer should be $2$ but instead in a math problem they use it as $-1$. Is this possible? thanks
0
votes
0answers
27 views

Number of solutions to a modular equation of a specific form

I struggle with this Exercise, or at least the part where one should prove how many solutions there are: Let $p$ be an odd prime, and let $e\in\mathbb{Z}$ with $e\gt 1$. Let $a$ be an integer of ...
1
vote
1answer
36 views

Prove that p is a quadratic residue mod $\frac{p^2+3p-2}{2}$

Let p be a prime number. Suppose that $q = \frac{p^2+3p-2}{2}$ is also a prime number. Prove that there is some integer $x$ so that $x^2 \equiv p$ (mod q). I assume I'm supposed to use quadratic ...
0
votes
0answers
30 views

Decrypting RSA message

I need help with a practice problem for an upcoming test. I've learned the answer to the problem is "well done", but don't know how to get there. Any help is greatly appreciated. Suppose that the RSA ...
2
votes
1answer
45 views

Corollary to Fermat's Little Theorem

A consequence of Fermat's Little Theorem If $p$ is prime and $a \in \mathbb{Z}$ not divisible by $p$, $a^{p-1} \equiv_{p} 1 $ is If $p$ is prime and $a \in \mathbb{Z}$ then ...
-1
votes
0answers
20 views

How can I check which numbers are prime in a residue class modulo n? [on hold]

If D = {0,1,2,3,4,5} (mod 6), then which elements of D are prime? In general, how can I check which numbers are prime in a residue class modulo n?
0
votes
3answers
65 views

Determine: $13^{-1} \pmod {67}$

Determine: $13^{-1} \pmod {67}$ I'm not sure how to deal with the negative one here as it inverts the integer? Any help would be appreciated!
0
votes
5answers
80 views

Calculate: $16^{4321}\pmod{9}$

How to calculate: $16^{4321}\pmod{9}$ I think I have to use the Euclidean Algorithm for this or Fermat's Little Theorem but im really at a loss here. Anyone knows how to do this?
2
votes
0answers
30 views

A property on finite sequences $1,1,x_2, x_3, \dots, x_{n-1}$ with $x_i \in \{0,1\}$

Consider a finite sequence $$x_0, x_1, \dots, x_{n-1}$$ with $n$ odd, all $x_i \in \{0,1\}$ and in particular $x_0 = x_1 = 1$. Furthermore, assume that the number of nonzero $x_i$ is even and $\leq ...
2
votes
1answer
51 views

Determining a multiple of a power of 2.

I am thinking about this question which I believe is a possible GRE question. "Which of the following numbers is exactly divisible by 32? A) $1.9 \times 10^5 $ B) $1.9 \times 10^6$ C) $1.9 \times ...
1
vote
2answers
22 views

Confused about a neither statement and modular

I am trying currently in the process of learning proofs involving congruence of integers with methods of direct and contrapositive and proofs with cases. However, I am quite confused by this statement ...
3
votes
3answers
51 views

Prove that $24^{31}$ is congruent to $23^{32}$ mod 19.

According to my knowledge, to prove that $24^{31}$ is congruent to $23^{32}$ mod 19, we must show that both numbers are divisible by 19 i.e. their remainders must be equal with mod 19. Please correct ...
6
votes
1answer
38 views

Can I apply Chinese remainder theorem here?

A number when divided by a divisor leaves $27$ remainder. Twice the number when divided by the same divisor leaves a remainder $3$. Find the divisor. My attempt: Let, the number be=$n$ and the ...
1
vote
2answers
15 views

Prove that if $ab \equiv cd \pmod{n}$ and $b \equiv d \pmod n$ and $\gcd(b, n) = 1$ then $a \equiv c \pmod n$.

Prove that if $ab \equiv cd \pmod{n}$ and $b \equiv d \pmod n$ and $\gcd(b, n) = 1$ then $a \equiv c \pmod n$. From this we know that $\gcd(d, n) = 1$. I can't derive anything else. Please help. ...
0
votes
1answer
24 views

Simple question about divisibility and modular arithmetic

Is the following true? Fix an $n\in \Bbb N$ which is not a multiple of $5$. Then for every $l\in\{0,\cdots,n\}$ there exists a $k\in \Bbb N_0$ with $5k\equiv l \mod n$. If yes, how do we prove it?
0
votes
5answers
34 views

Let a and b be positive integers and suppose that, for every positive integer c, we have that $a\equiv b\pmod c$. Then, $a=b$.

Let c be any positive integer. Suppose $a\equiv b\pmod c$. Then, $c\mid b-a$. Now what? I feel like I only have one tool at my disposal, namely divisibility: to say that $c\mid b-a$ means that ...
0
votes
1answer
47 views
1
vote
3answers
33 views

Finding Maximum Mod

Given a set of numbers, say $x=\{1,2,3\}$, how can I find the maximum $m$ such that $x_i\bmod m =x_j\bmod m$, where $i$ and $j$ are some indexes of the set $x$. So for $x=\{1,2,3\}$, the answer should ...
1
vote
2answers
37 views

Can you show that $3n+1$ is not divisible by $5$ using congruences?

I'm trying to prove that the difference of two consecutive cubes is never divisible by $5$, and I got to a point where I would have to prove that $3n+1$ is not divisible by $5$, where n is an integer. ...
0
votes
1answer
19 views

Modular Arithmetic and divisibility proof

I could use some help with this proof. Let $n, m ∈ Z^+$ and $a, b ∈ Z$. Suppose that $ a ≡ b$(mod n) and $a ≡ b$(mod m) and $(m, n) = 1.$ Show that $a ≡ b$(mod mn). From what I understand, it is ...
0
votes
0answers
26 views

Complexity of modular multiplication

By considering the method long multiplication, how to informally prove that modular multiplication of two number of length $m$-bit each has a complexity of $O(m^3)$? Tried this Taking two number of ...
2
votes
2answers
26 views

Proving that for every prime number $p$ there exist $a,b \in \mathbb{Z}$ such that $-1 \equiv a^2+b^2\ (mod\ p)$

How can I prove that for every prime number $p$ there exist $a,b \in \mathbb{Z}$ such that $-1 \equiv a^2+b^2\pmod p$?
1
vote
2answers
26 views

For which primes $p\not=2$ is $5$ a square mod $p$?

For which primes $p\not=2$ is $5$ a square mod $p$? Using the Legendre symbol, $5$ is a square modulo $p$ if $$\left(\frac{5}{p}\right)=5^{\dfrac{p-1}{2}} \equiv 1 \pmod{p}$$ Now we have ...
1
vote
1answer
21 views

Every positive integers of the form $4k+1$ can be factored into Hilbert primes

How can I show that every positive integer of the form $4k+1$ can be factored into Hilbert primes? A Hilbert prime is defined as a positive integer of the form $4k+1$ without a smaller factor of this ...
0
votes
2answers
29 views

Finding the inverse of a mod

How come $5^{-1} \pmod{2436} = 1949$? What are the steps to calculate it? This is what I tried: $5 \cdot I = 1 \pmod{2436}$
0
votes
0answers
12 views

Exponent operation over elements of $G$

I found a definition of an exponent operation over the element of $\mathbb{G}$ in this paper (page 4): $$ (g^a)^{\% b} = g ^{a \text{ mod } b}$$ I couldn't understand the rest of the paper (Decrypt ...
-1
votes
1answer
33 views

Prove that (m+n) mod d = (a+b) mod d if m mod d= a and n mod d = b [closed]

I'm trying to solve the proof mentioned in the title using the additional information below: m , n , a,b,d are all positive integers, and (m+n) mod d = a+b
2
votes
1answer
25 views

Classification of moduli where relatively prime numbers squared are 1

I came across an interesting property of certain numbers with respect to modular arithmetic and I was wondering if anybody had any more information about them. Consider an integer $n$ such that if ...
1
vote
1answer
45 views

For which $n$ in $\mathbb Z/n\mathbb Z$, $\bar{2}$ has a multiplicative inverse.

I am looking for which $n$ in $\mathbb Z/n\mathbb Z$, $\bar{2}$ has a multiplicative inverse. Attempt: I know that I need a $\bar{k}$ such that $\bar{k}$$\bar{2}$ $= \bar{1}$. I believe that the ...
1
vote
1answer
25 views

Conditions for existence of quadratic residue congruent to 1

Under what conditions are we guaranteed an existence of quadratic residue 1 other than squares of 1 and -1. What conditions a number must satisfy to have such residue.
2
votes
1answer
29 views

How to find a square root mod $pq$ given that $p \equiv q \equiv 3 \pmod 4$

Let $n = pq$ where $p$ and $q$ are prime. We do not know $p$ and $q$. All we know is that $p \equiv q \equiv 3 \pmod 4$. From this we need to find a number $y$, in terms of $n$ and $x$, such that $y^2 ...
0
votes
2answers
27 views

Divisibility of Exponents

So I'm having trouble trying to show this, a,b and x are positive integers. If $a\mid b^x$, show that some factor $k$ of $a$ divides $b$. In other words, if a number $a$ divides a power, how can I ...
2
votes
1answer
36 views

Is there a simpler way to do this modulo operation?

Question is: $38^7 \pmod{3} \equiv $ ? I do this: $38^7 \pmod 3 \equiv [(38 \pmod{3})^7]\pmod{3} \equiv [2^7] \pmod{3} \equiv 128 \pmod{3} \equiv 2$ Is there a way to do this without ...
1
vote
2answers
21 views

Connection between quadratic residue of a number to its factors'

Is it true that, If $N$ is product of two coprime numbers greater than 1. Quadratic residues of these numbers are quadratic residue of $N$ and vice versa? Can someone point me to a proof or show me if ...
5
votes
3answers
189 views

Riddle similar to the 100 prisoners riddle, but different

The riddle goes like this: $\qquad$ There are $100$ prisoners standing in line, each with a number on their back. The numbers are all different, and range from $1$ to $101$ (i.e. one number is ...
0
votes
0answers
29 views

Question about the solutions to quadratic congruence $x^2\equiv -1(\mbox{mod}\;p)$

As is known to all, when $p\equiv 1(\mbox{mod}\; 4)$, there are 2 solutions to the congruence in the set $\{1,2,3,...p-1\}$: $$x^2\equiv-1(\mbox{mod}\;p)$$ which to be exact are ...
-2
votes
1answer
35 views

Finding the digit in the units place [closed]

Find the digit in the units place of the number $2009!+3^{7886}$. The options available are: a) $7$ b) $3$ c) $1$ d) $9$
1
vote
0answers
38 views

simplifying a sum with modular arithmetic

Let $p\!\geq\!3$ be a prime and $n\!\in\!\mathbb{N}$. For $i\!=\!1,\ldots,n$ let $w_i\!=\!2i\!-\!n\!-\!1$. Let $n\%p$ denote the remainder in the integer division of $n$ by $p$. Can the following sum ...
0
votes
1answer
19 views

Proof that $t^m=t^{j}$ if $t$ is an $r^{th}$ root of unity such that $r \mid k$.

I need help with the following proof. Let $j$ = $0,1,\ldots, k-1$. Also, let $t$ be an $r$th root of unity other than $t=1$ such that $r \mid k$. We know $m=j\pmod k$. Furthermore, $m$, $j$ and $k$ ...
1
vote
1answer
29 views

Fermat's little theorem's proof for a negative integer

I'm in the process of proving Fermat's little theorem. For a prime integers $p$ we have $a^p \equiv a \mod{p}$ I proved it for a non-negative $a$, not I need to generalize the case to an ...
0
votes
1answer
21 views

Find modular arithmetic within a range.

When we execute any modular arithmetic say $a \pmod n$ then it results $0$ to $n-1$. But I need to find out a result within a range say $m$ to $n-1$. Is it possible? If then how?
1
vote
1answer
22 views

$2^i \equiv 2^j \pmod n$ implies $2^{j−i }\equiv1$ if $n$ is odd; also if $n$ is even?

Show that, if $0 \leq i < j$ and $2^i \equiv 2^j \pmod n$ and $n$ is odd then $2^{j−i} \equiv 1 \pmod n$. Is this necessarily true if $n$ is even? I have tried to prove this by using Fermat's ...
0
votes
0answers
25 views

How do you evaluate the quadratic residue of 7 mod p?

How do you evaluate this quadratic residue? I've been playing around with some specific values and I suspect 1 if p is of the form 28k+/-1, 3, 9 and -1 if 28k+/- 5, 11, 13. I have no idea how to come ...
1
vote
1answer
33 views

Find the modular arithmatic of mod p mod q.

I have an expression say $$x = ((a \bmod p) \bmod q)$$ Now given $x, p,q$, I need to find out the actual value of $a$. How can I do it? For an example I have: $$p = 109,\quad q = 26,\quad a = ...
2
votes
0answers
27 views

Generating function for the Josephus Problem?

According to the Wikpedia article on the Josephus problem, the general solution is by dynamic programming. However, since there seems to be an explicit recurrence rule for the problem, should there ...