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

3
votes
3answers
57 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
40 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
16 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
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
117 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
49 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
38 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
36 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
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
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
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
31 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
2answers
196 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
30 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

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
43 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
34 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
28 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
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
21 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
28 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 ...
0
votes
1answer
45 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$ ...
0
votes
3answers
30 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..
-1
votes
1answer
52 views

Assuming that it was enciphered with a generalized Caesar cipher with multiplier…

Assuming that it was enciphered with a generalized Caesar cipher with multiplier $r$ and shift constant $s$, find $r$ and $s$ and decipher the message: ZWSTO BPJOG BYQIP JOUWO OZGVS MPJOS MPQAI So ...
0
votes
1answer
36 views

Is it possible to make ABC from these rules?

Okay so we were asked this question the other day. I've given it a decent chunk of my life already and like any reasonable confused person, I have naturally turned to the internet for help. The game ...
4
votes
1answer
41 views

Proving that $y$ is a square mod $p$ and $-y$ is square mod $q$

Given that $p, q \equiv 3 \pmod 4$, neither $y$ nor $-y$ has a square root mod $pq$, and that $y$ is invertible mod $pq$, how would I prove that $y$ is a square mod one of $p, q$ and $-y$ is a square ...
0
votes
1answer
27 views

How to find a integer using modular arithmetic

Hi guys, I'm preparing for my maths exam in 2 weeks and these sorts of questions come up every year. Unfortunately I was out when the lecturer taught us how to do these and I looked up his notes but ...
1
vote
1answer
28 views

Finding multiples of three given a few simple rules

We were given this problem the other day and it seems a little over my head, so I thought I'd share it here for any possible advice or assistance :). The problem is as follows: Initially, $x = 1$. ...
1
vote
1answer
65 views

Preserving modulus residue under division

Modulus residue is preserved or honored (sorry, I don't know the correct term. Is it homomorphism?) under addition and multiplication. For example: 2 + 4 = 6 2 * 4 = 8 Then, making those values ...
-1
votes
0answers
29 views

Finding unknown in modular arithmetic.

I know how to work something like $19x \equiv 4 \pmod{141}$ (using the method of checking if $141$ divides $19x - 4$ when $x = 0,1,2, \ldots$), but for some reason, I don't know how to solve an ...
1
vote
1answer
43 views

Is this result correct? If so, where does it come from?

$$ a^{nr} \mod 10 \equiv (a^n \mod 10 )^r \mod{10} $$ I'm not sure if this result holds, I haven't taken any real number theory. My notation is most likely wrong however my thinking is the following ...
2
votes
1answer
23 views

Proof of $a^{m \, \pmod{\varphi(n)}} \equiv a^m\pmod n$

I am currently studying modular arithmetic for a course in cryptography. I have proved many operations, but I am stuck in one: Assume $n,a\in \mathbb{N}$ and $n\ge 2$. Prove that if $\gcd(a,n)=1$ ...
0
votes
0answers
17 views

How does the Chinese Remainder Theorem help breaking the Diffie Hellmann Problem?

on http://crypto.stackexchange.com/questions/30328/why-does-the-modulus-of-diffie-hellman-need-to-be-a-prime/, i asked about why the modulous in the Diffie Hellmann Key Agreetment needs to be a prime. ...
1
vote
1answer
59 views

Proof verification for FLT when $n=3$

For: $$a^3 + b^3 = c^3$$ Why can't I simply take mod 3 ? The only possibility is when $a\equiv 0$ (mod 3) and $b\equiv 0$ (mod 3) But if this happens then 3 can be taken as a common factor. ...
1
vote
1answer
12 views

Explain this step in solving this system of linear congruences.

I'm looking at this example and it doesn't make sense to me. We have to solve the following systems of linear congruences : $x\equiv 1\pmod 5$ $x\equiv 2\pmod 6$ $x\equiv 3\pmod 7$ We take ...