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
1answer
19 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
12 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 ...
1
vote
3answers
55 views

Order of $5$ in $\Bbb{Z}_{2^k}$

Is it true that the order of $5$ in $\Bbb Z_{2^k}$ is $2^{k-2}$? I was unable solve the congruence $5^n\equiv 1\pmod {2^{k}}$ nor see why $5^{2^{k-2}}\equiv 1\pmod {2^{k}}$. I'm not sure if this is ...
0
votes
5answers
79 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
1answer
42 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
vote
1answer
48 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
votes
0answers
19 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
63 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!
1
vote
0answers
24 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 ...
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 ...
5
votes
2answers
243 views

Number Theoretic Transform (NTT) to speed up multiplications

I recently heard that the Number Theoretic Transform (NTT), which is a specialization of Fast Fourier Transformation (FFT) over the ring modulo an integer, can be used to speed up certain ...
3
votes
3answers
50 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 ...
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. ...
6
votes
1answer
37 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 ...
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
33 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 ...
3
votes
5answers
2k views

How do I subtract times?

I have an embarrassingly basic modular arithmetic question. I understand that I can subtract, for example, 1 hour from 10 o'clock to get 9 o'clock, or even 2 hours from 1 o'clock to get 11 o'clock; ...
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. ...
13
votes
3answers
534 views

Formula for occurrence of leap years in the Jewish calendar

Over at Judaism.SE, there was a discussion about a formula to determine leap years in the Jewish calendar. Basically, the calendar follows a 19-year cycle, and seven of those years -- 3, 6, 8, 11, 14, ...
3
votes
1answer
2k views

Find an inverse of $a$ modulo $m$ for each of these pairs of relatively prime integers

How would I find the inverse of a given number $a$ modulo $m$, given that $\gcd(a,m)=1$? a) $a = 2$, $m = 17$ $17 = 2 \cdot 8 + 1$ $2 = 1 \cdot 2 + 0$ $1 = 17 - 8 \cdot 2$ <-How do I know ...
5
votes
3answers
186 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 ...
7
votes
1answer
440 views

How to solve congruence $x^y = a \pmod p$?

I'm having trouble solving this congruence: $$x^{114} \equiv 13 \pmod {29}.$$ I thought that it made sense to try to solve it using this idea: "Suppose you want to solve the congruence $ x^y \equiv a ...
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 ...
1
vote
1answer
616 views

Solving a non-linear congruence

How can we solve for $x$, knowing the integer $n$ and the real numbers $a$ and $b$, the following non-linear congruence: $(x+a)^2=-b\pmod{n}$ Specifically in this example: ...
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 ...
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 ...
2
votes
2answers
25 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$?
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
11 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 ...
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 ...
-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
1
vote
1answer
44 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 ...
2
votes
2answers
181 views

Recursive Function - mod 5

How do the recursive function for $\mod 5(x) = 0$ rest of division of $x$ by $5$. $$\begin{align} \mod&5(5) = 0\\ \mod&5(6) = 1\\ \mod&5(7) = 2\\ \mod&5(8) = 3\\ \mod&5(9) = 4\\ ...
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
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.
4
votes
6answers
167 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 ...
0
votes
1answer
981 views

What will be the multiplicative inverse of square root of 5 with respect to a natural number $M$?

Can such a number $N$ be found such that $\sqrt{5}N \equiv 1 \mod M$? If no,what can be the best approximation for $N$?
2
votes
1answer
26 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
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 ...
3
votes
2answers
67 views

weird relation modulo

This is going to sound like a stupid question, but I cannot understand how I get this result (I understand why, but it looks like there is no relation). $p, q$ primes why do we have this? $p \cdot ...
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
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 ...
-2
votes
2answers
81 views

Generalised Fermat's Little Theorem [closed]

Prove the following generalization of Fermat’s little theorem: For every positive integer $n$, and every $ \alpha \in \mathbb Z_n $, we have $ \alpha^n = \alpha^{n-\phi(n)}$.
-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$
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
0answers
37 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 ...
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 ...