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

2
votes
1answer
40 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 ...
10
votes
0answers
92 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
58 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
60 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. Simply inserting f=0 contradicts the suggested number of solutions. Let $p$ be an odd prime,...
1
vote
1answer
37 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
35 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
47 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 $a^...
0
votes
3answers
69 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
88 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
125 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 (n+...
2
votes
1answer
56 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
24 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
59 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
45 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
19 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. Is ...
0
votes
1answer
25 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 $\...
2
votes
2answers
140 views

$ 1^k+2^k+3^k+…+(p-1)^k $ always a multiple of $p$?

I would appreciate if somebody could help me with the following problem: Q: For any prime number $p(p\geq 3), k=1,2,3,...,p-2$, why is $$ 1^k+2^k+3^k+...+(p-1)^k $$ always a multiple of $p$ ?
0
votes
1answer
57 views

Proof the following statement false – Every real number, a , can be written as $a=\frac{p}{q}$, where p and q are integers. [closed]

I really Faced Difficulties finding a counter example I really needed hints here.
1
vote
3answers
35 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
39 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
27 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
39 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 $$5^{\...
1
vote
1answer
23 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
30 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 ...
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
48 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
27 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
30 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 ...
-1
votes
2answers
32 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
37 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
22 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
2answers
202 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
32 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 $\pm\frac{p-1}{2}!(\...
-2
votes
1answer
37 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$
2
votes
0answers
44 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
20 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
37 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
22 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
31 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 = 171$$...
2
votes
0answers
29 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 ...
0
votes
1answer
22 views

To decrypt this version of Turing's code, does the decrypter actually need the secret key?

I am self studying MIT's Mathematics for Computer Scientists (link) There is a chapter in the readings on Number Theory, and it goes through the math involved in the cryptography methods used around ...
1
vote
2answers
29 views

Why can I cancel in modular arithmetic when working modulus a prime number?

Working modulus a prime number in modular arithmetic let's you cancel factors in a congruence equation. Let p and k be integers, p a prime number and k not a multiple of p: $a \cdot k\equiv b \cdot k\...
0
votes
1answer
46 views

Using an exponential cipher system, encipher the word HALT. where $p = 29, k = 11$, and $m = 1$.

Using an exponential cipher system, encipher the word HALT. where $p = 29, k = 11$, and $m = 1$. The progress I have made so far: H A L T $07, 00,11,19$ Since, $m =1$, we break this up into $2*m$ ...