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
38 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
17 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
54 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
18 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 ...
0
votes
5answers
63 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?
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
242 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
49 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
36 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
32 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
votes
0answers
39 views

Torelli Theorem [on hold]

Good Morning! I would like to know what are the minimum mathematical prerequisites for study the Torelli Theorem (algebraic geometry). I also accept bibliographic suggestions for this walking. Thank ...
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 ...
0
votes
2answers
34 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
185 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
615 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
24 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
43 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
180 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
165 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
80 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
64 views

Help me understand modular arithmetic(?) [closed]

I always had problems with modular arithmetic, I often used calculators for them but when it comes to manual calculating I dont know how to it. I have few examples I dont understand: 16^(-11) mod ...
-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
36 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 ...
0
votes
1answer
20 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?
0
votes
3answers
28 views

How do I prove the equivalence of these two congruences? [closed]

I have $7x\equiv 1\pmod8$.How do I prove it is equivalent to $x\equiv 7\pmod8$? I have no idea to start on this question.Thanks for any reply..