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
0answers
23 views

A primitive root exists modulo $n$ if and only if $n=2$, $n=4$, $n=p^k$, or $n=2p^k$ with $p$ an odd prime.

I have already proven that primitive roots exist modulo $p^k$ and $2p^k$ for an odd prime $p$. I'm having trouble proving the other direction. Is it simply due to the fact that if $p,q$ are distinct ...
0
votes
2answers
26 views

Find a prime $p$ satisfying $p \equiv 1338 \mod 1115$

Find a prime $p$ satisfying $p \equiv 1338 \mod 1115$. Are there infinitely many such primes. A little confused about this problem, any help or advice?
1
vote
2answers
608 views

Doing modular division when denominator and modulus not coprime

So normally if you calculate $n/d \mod m$, you make sure $d$ and $m$ are coprime and then do $n[d]^{-1}\mod m$ , all $\mod m$. But what if $d$ and $m$ are not coprime? What do you do?
1
vote
0answers
7 views

how to sum the divisors of N mod K if all I have is N mod K?

The input to this problem is N. I have to calculate 2 things: 1 - N! mod (10^9 + 7) 2 - sum of all divisors of N! mod (10^9 + 7) I know how to do the first step, I'm wondering if there is a way ...
3
votes
3answers
52 views

Finding all solutions for to the equation $x^3 = 0\ {\rm mod}\ 9$

How do I go about finding the solutions to: $$ x^3 = 0\mod 9 $$ Any help is greatly appreciated thank you
2
votes
2answers
42 views

Solving Simultaneous Equations - Hill Cipher

I have searched but an unable to find any examples like what I am faced with. Plaintext = SOLVED CipherText = GEZXDS 2x2 encryption matrix $$ \left(\begin{matrix} 11 & 21 \\ 4 & 3 ...
-1
votes
0answers
7 views

how to do DHM key exchange [on hold]

You want to use the Diffie-Hellman-Merkle Key Exchange with n=93, M=12 and a=20. Find α. What would the answer be? I can't figure out how to do this
5
votes
2answers
36 views

$x^2+1=0$ in $\mathbb{Z}_7$

$x^2+1=0$ in $\mathbb{Z}_7$ By trying each number, I see that there is no solution, is this correct? And could you help me with a more direct solution, since this method is not going to work for ...
2
votes
0answers
18 views

Divisibility in different Modulo.

So I've actually been working with congruences recently in class and most of the time I end up using Fermat or the Euler Totient function to simplify a large exponent. In general, I run into a ...
1
vote
1answer
25 views

Derivative of Diffie Hellman

Looking to get some clarification on this. We have the same three protagonists, Bob and Alice, trying to send each other a message. And Eve trying to figure out the message sent by Bob and Alice. ...
2
votes
5answers
62 views

How to prove that $8^{18} - 1$ is divisible by $7$ [duplicate]

How to prove that: $$ 8^{18}-1\equiv0\pmod7 $$ In the simplest way?
0
votes
1answer
15 views

Polynomial Arithmetic Modulo 2 (CRC Error Correcting Codes)

I'm trying to understand how to calculate CRC (Cyclic Redundancy Codes) of a message using polynomial division modulo 2. The textbook Computer Networks: A Systems Approach gives the following rules ...
0
votes
0answers
19 views

Proof modular equality by induction

I'm trying to prove using induction that $5^{2^{x-2}} = 1 + 2^x (\mod(2^{x+1}))$ So far, I have: Base case: $x = 2, 5 = 5 (\mod 8)$, It is true. $x = 3, 25 = 9 (\mod 16)$, It is true. Inductive ...
1
vote
2answers
23 views

Stuck with modular arithmetic problem using multiplication property

I have the following problem: Given $k\geq 1$, find $h$ such that $$2^h \frac{4^k-1}{3}-1 \equiv 0 ~(\text{mod}~3).$$ This is my attempt using the invariance of multiplication: $$2^h ...
0
votes
1answer
308 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$?
0
votes
2answers
13 views

If a is not relatively prime to n prove modulo property

If $n>1$ is integer and $1\le a \le n$ is integer such that $(a,n)\neq 1$ then prove there exist integer $1 \le b <n $ such that $ab \equiv 0(mod \; n)$ I have tried everything from going to ...
1
vote
1answer
61 views

Product of roots of unity

Does somebody have a nice proof of the following? $$\prod_{m=1}^{n-1} \frac{e^{2\pi i k m/n} - 1}{e^{2 \pi i m / n} - 1} = \begin{cases} 1 & \text{ if $\gcd(k, n) = 1$} \\ 0 & ...
3
votes
2answers
599 views

Solving Diffie–Hellman problem for low primitive root

What's a good way of solving the Diffie–Hellman problem when those exchanging the message have chosen a low primitive root $g$ (e.g. $g=3$)? Of course you could brute force it but I'm interested in ...
0
votes
1answer
30 views

If $a\pmod 3 \equiv 1$ and $b\pmod 3 \equiv 2$, then $ab \pmod 3 \equiv 2$

I'm stuck on this this problem: Let $a$ and $b$ be positive integers with $a\pmod 3 \equiv 1$ and $b\pmod 3 \equiv 2$. Prove that $ab \pmod 3 \equiv 2$. I think the first step for the direct ...
5
votes
5answers
315 views

polynomial with positive integer coefficients divisible by 24?

I have to show that $n^4+ 6n^3 + 11n^2+6n$ is divisible by 24 for every natural number, n, so I decided to show that this polynomial is divisible by 8 and 3, but I'm having trouble showing that it is ...
1
vote
1answer
24 views

What does the notation $\equiv 1\ (\text{mod}\ p)$ mean?

I'm trying to understand the Fermat theory : $a^{p-1} \equiv 1\ (\text{mod}\ p)$ I know that $a\ (\text{mod}\ p)$ gives the remainder of division of $a$ by $p$. So what is $\equiv 1\ (\text{mod}\ ...
0
votes
0answers
21 views

Modulo and power calculation [on hold]

Let $A{^-}{^n}$ mod X = ($A{^-}{^1}$ mod X )${^n}$ mod X for $n>0$ Now we want to compute $A^B$ mod X fro given A,B and X provided A and B are coprime. Note : $A{^−}{^1}$ mod X refers to the ...
1
vote
2answers
27 views

Modular Inverse

Calculate the Following $ (2^{19808}+6)^{-1} +1$ Mod (11) I'm completely lost here for several reasons. First of all the large power of 2 just throws me off and secondly I've seen inverse equations ...
0
votes
1answer
23 views

Obtain Base in this equation

If we have below equation and know that $6$ and $3$ are answers of this equation obtain base of these equation: $$X^2 - 11X + 22 = 0$$
5
votes
9answers
8k views

Explain for students: Why does 0 mod n equals 0 (zero)?

I told my students that the mod operator basically gives the remainder of division, so upon seeing: 0 mod 10 Some students (apparently) reasoned that, "10 goes ...
3
votes
2answers
39 views

How many group homomorphisms are there from Zn to Zm?

In looking up this question, I found this site: Physics Forums. In it, someone claims that $f(x) = kx$ is a homomorphism from the group $\mathbb{Z}_{m}$ to $\mathbb{Z}_{n}$ if $m$ divides $kn$. I ...
-1
votes
2answers
30 views

Find the value of X when X is positive intigers. [on hold]

I'm doing my brothers homework but he don't know how to do this.Find the answer of the equation below. $$2555^{2012}+2012^{2555}≡x\pmod{11}$$
0
votes
1answer
28 views

Calculus showing with mods

I got this problem from my Calculus II teacher, I have no idea how to approach it... Show that if $a,b,c$, and $d$ are integers such that $a\equiv b\pmod m$ and $c\equiv d\pmod m$, then $a+c\equiv ...
-2
votes
1answer
24 views

Finding the remainder given another dividend, divisor, and remainder [closed]

The remainder when the positive integer k is divided by 7 is 3. What is the remainder when 3k is divided by 7?
2
votes
1answer
26 views
0
votes
2answers
19 views

Square roots and modular arithmetic

Find 4 different square roots of: I have no idea how to get started on this, could someone explain what the first step would be?! a. 1mod35 b. 1mod77
0
votes
2answers
66 views

Day of the week from the date.

I still remember when I was a kid some senior student used to ask us a date from history and then tell us what day was then within 20 seconds. I read montgomery's Number theory and when found the ...
1
vote
3answers
24 views

How to simplify this alternating modulo expression?

The value of $(1000^i \mod 7)$ alternates between 1 and 6, as such: $$ 1000^0 \mod 7 = 1 $$ $$ 1000^1 \mod 7 = 6 $$ $$ 1000^2 \mod 7 = 1 $$ $$ 1000^3 \mod 7 = 6 $$ But as $i$ grows larger, these ...
0
votes
3answers
19 views

Modular Arithmetic: using congruence to find remainder

How do I use the fact that if $a = b \pmod n$ and $c = d\pmod n$ then $ac = bd\pmod n$ to find the remainder when $3^{11}$ is divided by $7$?
2
votes
3answers
26 views

Integer solution to multiple modular arithmetic equations

So i understand how to do this when it is just x, but now with multiples of x I am a little confused, and there's no example in my textbook of this. I just need a push in the right direction for how ...
0
votes
2answers
37 views

modular arithmetic congruence

Simplify the following congruence: $$−169 \equiv \text{ ?} \mod 52 $$ (By simplify, we mean find the smallest non-negative whole number which is congruent to $-169$ modulo $52$.) Simplify the ...
1
vote
2answers
41 views

Modular Arithmetic/Number Theory

(Not really sure about my work, so if you could tell me if I am on the right track that would be great!) Find an integer x so that: a. $x\equiv1\pmod{13}$ and $x\equiv1\pmod{36}$ Using the ...
-1
votes
2answers
19 views

modular arithmetic multiplicative inverse of 12 [closed]

Which of the following have multiplicative inverses modulo 12? (Select all that apply.) A. 6 B. 9 C. 10 D. 1 E. 8 F. 4 G. 3 H. 7 I. 2 J. 5 K. 11
-2
votes
1answer
27 views

How can i do this algebra question?

The question is show that the relation $a\sim b$ defined by $a\equiv b \bmod 7$ is an equivalence relation on $\mathbb{Z}$. How many equivalence classes are there? Let us call them $[0]$, $[1]$, ..., ...
0
votes
0answers
18 views

Recurrences with modulo

Is there any specific way to solve recurrence of form (example): $$f(x) = (a \cdot f(x-1) + c) \bmod{r} $$ (when recurrence involves modulo). For recurrence without modular arithmetic I could use ...
0
votes
4answers
32 views

Calculating $3/10$ in $\mathbb{Z}_{13}$

I'm trying to calculate $\frac{3}{10}$,working in $\mathbb{Z}_{13}$. Is this the correct approach? Let $x=\frac{3}{10} \iff 10x \equiv 3 \bmod 13 \iff 10x-3=13k \iff 10x=13k+3$ for some $k \in ...
1
vote
5answers
1k views

Prove that the sum of three consecutive squares, minus two is a multiple of 3

Prove that if you add the squares of three consecutive integer numbers and then subtract two, you always get a multiple of 3.
0
votes
2answers
17 views

Rever direction modulo operator?

This: i = ((i + 1) % itemArray.length assigns to i the next space going towards the right in a circular manner. Is there a way ...
0
votes
1answer
33 views

$a^n = a$ mod ($n$)

Is the following a valid proof Let $a = g^k$ mod $n$ where $g$ is a primitive root of $n$ $a^n = (g^k)^n \text{mod} (n) = (g^n)^k \text{mod }(n) = g^k \text{mod}(n)$ [as $g^n = g$ mod $n$] $= a$ ...
2
votes
1answer
79 views

Prove that $r(2^{55555})$ divisible by $5^5$

In this question there is a comment by @amclade, that $$r\left(2^{55555}\right) \equiv 0 \pmod{5^5},$$ where $r : \mathbb{N} \rightarrow \mathbb{N}$ function gives the reverse of a number. I've ...
0
votes
2answers
26 views

Find the least positive residue of $5^{16} \bmod 17$

I need some help on finding the least positive residues. Not sure what the correct approach is to take on these types of problems and the book I'm reading isn't helping me. ** UPDATE ** If 17 was ...
1
vote
2answers
59 views

Can this be solve using modular arithmetic? $k$ is prime $\Rightarrow$ $8k+1$ is prime

Is the following statement true or false? $\forall k \in \mathbb{N}, k$ is prime $\Rightarrow$ $8k+1$ is prime The answer is that the statement is false because if $k=7$, then $k$ is prime but ...
1
vote
0answers
52 views

Find all numbers $x$ satisfying $x^3 \equiv 1 \pmod A$.

Given any two numbers $M,N \in \{1,2,\ldots,10^{18}\}$, find all numbers $x$ lying between $M$ and $N$ satisfying $$x^3\equiv1 \pmod A,$$ where $A$ can be any number. I know the case when A is even. ...
0
votes
2answers
32 views

How do I count all values that satisfy X mod N=1 in the range [A,B]

I want to count how many values of x in range [A,B] give remainder of 1 when divided by N. Is there any formula I can apply?
0
votes
1answer
44 views

Calculate$ (n+m-1)C_n \mod 10^9+7$ efficiently

I want to calculate $(n+m-1)C_n \mod 1000000007$. where $n$ can be between $1$ and $10^9$. $m$ will not exceed $30$. How do I calculate it efficiently.