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

Check proof of Fermat's Little Theorem

I wrote an informal proof of Fermat's Little Theorem. Can someone check to see if the reasoning is valid, and if so how I could formalize it: Theorem: $n^{p-1} \equiv 1 \pmod p$ $ n \times 2n ...
2
votes
1answer
272 views

Find period of power sequence $a^k \mod m$, with $a, m$ not coprime

Let $a, m$ be positive integers and $m > 1$. I'm interested in the sequence $(a^k)_{k \in \mathbb{N_0}} \mod m$. Since there are only $m$ different values that can occur in the sequence and since ...
3
votes
3answers
61 views

Prove $\{x \mid x^2 \equiv 1 \pmod p\}=\{1, -1\}$ for all primes $p$ [duplicate]

One way to prove that $\{x \mid x^2 \equiv 1 \pmod p\}=\{1, -1\}$ is to use the fact that $\{1, -1\}$ is the only subgroup of the cyclic group of primitive residue classes modulo $p$ that has the ...
1
vote
2answers
218 views

Given integers $a \ge b > 0$ and a prime number $p$, prove that ${pa \choose pb} \equiv {a \choose b} \mod p$.

I've been grappling with this problem for a while but haven't solved it. Given integers $a \ge b > 0$ and a prime number $p$, prove that ${pa \choose pb} \equiv {a \choose b} \mod p$.
1
vote
1answer
45 views

Determine $2$ missing digits for modulo $11$

An account number verification system works as follows: All digits in a 10-digit account number all multiplied by following weights: $$(6 \ 3 \ 7 \ 9 \ 10 \ 5 \ 8 \ 4 \ 2 \ 1)$$ Resulting numbers ...
1
vote
2answers
33 views

Computing modular inverses for a sequence of numbers

I have a prime $p$ and an integer $L$ such that $p \gg L \gg 1$, and I need to compute modular inverses of numbers $1, 2, \ldots, L$ (modulo $p$). Obviously I could apply the extended gcd algorithm to ...
0
votes
2answers
26 views

Relations & modular artithmetic

Given the following partition on the set N:{ n being natural : n = 7k+p} , where p= 0,1,2,3,4,5,6. 1) Find an equivalence relation ~ on the set N that partitions N into the sets mentioned in the ...
0
votes
4answers
130 views

how to determine the modulo rules?

I´m repeating some old math exercises and could`t remember the following modulo rule: I have to find the smallest natural $k>0$ $mod(3^k,7)=1$ the solution seems straight forward. But I dont ...
0
votes
1answer
42 views

Modular exponentiation with Straightforward method

I would like to understand who it works the modulo with Straightforward method. For example I try to test this: 290 mod 1009 = 257^x mod 1009. Which is the "x"? ...
-1
votes
1answer
122 views

Why is this number always divisible by $p^2$

For any prime $p > 3$ it seems that if you look at the number $1^{-1} + 2^{-1} + \cdots +(p-1)^{-1}$ it will be divisible by $p^2$. It's easy to see that it's divisible by $p$, because you're just ...
1
vote
0answers
20 views

Sufficient condition for an equivalence

What is a sufficient condition for the equivalence $$ a_1 \uparrow a_2 \uparrow ... \uparrow a_n \equiv a_1 \uparrow a_2 \uparrow ... \uparrow a_n \uparrow a_{n+1}\ mod(\ m)\ ? $$ In a closely ...
0
votes
2answers
95 views

How to check if a function is an homomorphism?

For example: Let $$f:\mathbb{Z}_{60} \rightarrow \mathbb{Z}_{12} \times \mathbb{Z}_{20}$$ $$[x]_{60} \mapsto ([x]_{12} , [x]_{20})$$ Prove that it's well defined Check if it's a ring homomorphism ...
2
votes
2answers
555 views

Making the water gallon brainteaser rigorous

This is a classic brainteaser. Suppose I have two water jugs of size 4 gallons and 7 gallons, and an infinite amount of water supply. I'm allowed to fill up a gallon completely, pour water into a a ...
1
vote
1answer
85 views

How is statistical uncertainty calculated for the modulus function?

I know it's an unusual function to calculate an uncertainty for, but I haven't been able to figure out a reasonable means for calculating derivatives for it to do so myself. I know modular arithmetic ...
0
votes
1answer
70 views

Infinite “Twins” in reduced residue systems modulo primorials

The Lth primorial ($p_L\#$) is the product of the first L prime numbers. The reduced residue system modulo $p_L\#$ is any set of positive integers with cardinality equal to the totient of $p_L\#$ ...
0
votes
2answers
93 views

Finding invertible elements in $\mathbb{Z}/m\mathbb{Z}$

Can anyone show me how to find invertible elements in $\mathbb{Z}/m\mathbb{Z}$, $m$ is say $28$? Also I'm not very clear about what it mean by 'invertible element in $\mathbb{Z}/m\mathbb{Z}$'
0
votes
2answers
83 views

What are all the invertible elements in $\mathbb{Z_m}$ for $m = 30$? [duplicate]

How can I know all of the invertible elements? Is it just all of the numbers that are relatively prime to 30?
0
votes
2answers
80 views

Computing modulus by hand

Can someone please explain how you would compute the following modulus by hand? 7503 mod 81 -7503 mod 81
0
votes
3answers
212 views

Calculating 2 rightmost decimal digits of large number (modular exponentiation)

I'm asked to calculate 2 rightmost decimal digits of large number, e.g. 3^2005. The hint is to use some modular trick (probably Euler phi function). Can anyone show me how to reduce the exponent?
1
vote
1answer
164 views

How do I row reduce a matrix mod 26 when it is singular mod 26?

Cryptography assignment question: matrix $A$ is \begin{equation} A = \left(\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 3 & 1 \\ 0 & 2 & 5 ...
0
votes
2answers
59 views

Confusion on how to find answer to $11^{-1}\mod 26$

I'm confused how to find solutions to questions like $11^{-1}\mod 26$ and others like these. The solution is $19$ but I don't understand how. $11^{-1}$ on its own is $\frac{1}{11}$. Thanks
2
votes
1answer
97 views

Properties of modular arithemtic mod primes and quadratic residues

I have the following two equations: $$z_1 = x_1^2 \pmod p$$ $$z_2 = x_2^2 \pmod q$$ and p and q are prime. and I want to show $x^2$ and $z^2$ are equal mod pq $$x^2 = x_1^2 c_1^2 + x_2^2 c^2_2$$ ...
0
votes
1answer
34 views

Jacobi Symbol To Determine Quadratic Residue

I have an exam tomorrow and I have no idea how I would do this type of question and I'm pretty sure its coming up can someone please help me out by maybe doing one as an example and explaining what ...
1
vote
2answers
208 views

Fast method for solving modular exponential function with semi-prime modulus

Assume we have a semi-prime $N = pq.$ Assume $N$ is not divisible by $2$ or $5$. We want to solve the equation $$10^x \equiv 1 \mod N, \ \ \ x>0.$$ One solution is enough. Is there any fast method ...
3
votes
0answers
83 views

Find n's for which $P_n$ is prime.

Consider the numbers $P_n=(3^n-1)/2$. Find $n$'s for which $P_n$ is prime. Conjecture: If $n \equiv 1 \mod 6$, and $n$ is prime, then $P_n$ is prime. I have tried proving this by contradiction but ...
5
votes
5answers
202 views

Intuition of why $\gcd(a,b) = \gcd(b, a \pmod b)$?

Does anyone have a intuition or argument or sketch proof of why $\gcd(a,b) = \gcd(b, a \pmod b)$? I do have a proof and I understand it, so an intuition would be more helpful. The proof that I ...
0
votes
1answer
98 views

Finding the generator

In the discrete log problem we have to find the exponent, which is a hard problem but what if instead we wanted to find $a$ (the generator). I couldn't find it if there is already a question about it. ...
4
votes
1answer
86 views

Find all $x,y\in\mathbb{Z}$ s.t $2x^3-7y^3=3$

Find all $$x,y\in\mathbb{Z}$$ such that $$2x^3-7y^3=3$$ Solution: We consider first $$2x^3-7y^3\equiv3 \pmod 2$$ $$5y^3\equiv 1 \pmod 2$$ $$y^3\equiv 1 \pmod2$$ which has solution $y\equiv 1 ...
1
vote
1answer
33 views

Help understand lecturers example

My lecture gave us the following example and I am having trouble following it Would √23(mod 209) not become √23(mod 11) and √23(mod 19)? How is he getting √4? And also I do not know how to use the ...
0
votes
3answers
1k views

Opposite of mod in a equation

I am trying to solve this module equation (due to a cryptography program that I am coding) but cannot figure it out how: X + 7 % 10 = 6 How Do i solve this? Thanks in advance.
0
votes
1answer
62 views

Solving an equation with modular arithmtics

Consider a machine that operates on the set of real numbers using the following equation: O = X × [(I + Y) mod L] − Z, where I is the input and O is the output of this machine. L is known and it is ...
2
votes
0answers
88 views

Lucas Number Equivalent of the Pisano Period?

I'm doing some work with the Pisano Period, and it's leading to also talk about the Lucas numbers $mod \ m$, and their period. Is there a specific notation already designated? Sticking with using a ...
4
votes
2answers
72 views

Is this a helpful way of thinking about modular arithmetic?

Could one consider the structure of $\mathbb{Z_{n}}$ under addition and multiplication to simply be that of the ordinary integers, with one additional axiom - namely that $n=0$? So we would have ...
0
votes
1answer
86 views

What does “Ord” mean

I have a question as follows: Solve for x: Ord29(x)=7. I have never seen Ord before I have an exam and something like this will come up so can someone just tell me how I would go about doing this?
1
vote
2answers
53 views

Deriving formula for when a number will have a unique cubed root

I have a question as follows and I am pretty sure it is going to come up on my exam Under what condition on $p$ will a number have a unique cube root $\mod p$, where $p$ is a prime number? Derive an ...
1
vote
2answers
198 views

Evaluate the Cubed Root

So I have a question as follows Evaluate the cube root of $2 \mod 59$ So it is my understanding that I need to find $x$, where $x^3 = 2 \mod{59}$ I have tried different values for $x$ all the way ...
0
votes
0answers
51 views

How to use Mod operator if I don't have it?

This is the list of function/operators I can use in a software. There isn't the mod operator (neither %). So I want it, such as: $ 1\mod 4=1$ $ 5\mod 4=1$ ...
0
votes
1answer
134 views

ElGamal Public Key Cryptosystem and Digital Signature Scheme

I'm tryting to understand how ElGamal algorithm works, and I got the following example, and I couldn't understand one part of this: A) P=23, g=5. B) x=3, then y=10 (for 53 mod 23=10 ). C) Sign for ...
1
vote
0answers
108 views

Question about tetration modulus a prime $p>100$

Define $x§y$ as the power tower : $x^{x^x...}$ where $...$ means $y$ times. For instance $2§1=2,2§2=4,2§3=16,2§4=2^{16}$. See : http://en.wikipedia.org/wiki/Tetration Let $p$ be a prime larger than ...
1
vote
1answer
77 views

Probabilistic time algorithm for finding the solution for quadratic congruences (case when p is prime)

I was trying to solve the following equation: $$y = x^2 \bmod p$$ where $p$ is prime. I was trying to find an algorithm that solved this and that was in BPP (I don't think there is one in P). I ...
1
vote
3answers
50 views

Help with the proof for modulo multiplication

My lecturer's powerpoint has the following proof but I feel like it's missing a step. Could I get some help with how the final conclusion is reached. Thank you. For multiplication, since we know that ...
2
votes
2answers
110 views

Perfect divisibility for products in modular arithmetic

Say we have that $z^2 - x^2 = 0 \ ( \ mod \ p)$ that implies: $p \ | \ (z-x)(z+x)$ However I was not 100% sure how that implies about the divisibility of p towards $(z-x)$ and/or $(z+x)$ and ...
0
votes
2answers
63 views

Modulo double check

I'm working on some math, and this is the equation that I have to write an extensive computer program for. Wolfram Alpha gives this same answer, so I just want to double check to know WHY this is the ...
12
votes
3answers
805 views

Fermat: Last two digits of $7^{355}$

I am doing this problem mentioned above and I know the answer because I know Euler's Theorem that $$a^{\varphi{(m)}}\equiv{1}\pmod{m}.$$ I used 100 as my modulus and got that the last two digits of ...
0
votes
2answers
82 views

Explanation of $d^{-1}$ in modular arithmetic [duplicate]

I wasnt quite sure what to name this question, so that's what it is. I'me working on an encryption system, and I need modulus. I already asked a question on this, here, and I cannot figure out the ...
0
votes
1answer
147 views

How to find positive integers where the multiplicative modular inverse is equal to itself for mod n?

This a question sparked from Project Euler Question. I really devoted so much time to search an efficient solution however no output. What are some possibles theorems or formulas that are useful in ...
0
votes
2answers
66 views

Define S as a set of primes such that if a, b are in S, ab+4 is in S. Show that S must be empty.

Define $S$ as a set of primes such that $(a \in S) \land (b \in S) \implies (ab + 4) \in S$ [$a$ and $b$ can be the same number]. Show that $S$ must be empty. A hint is given ... "work modulo 7." ...
3
votes
3answers
3k views

Modular Arithmetic - Find the Square Root

Okay so I am in college and in the notes it shows this example: // Example: Compute the square root of 3 modulo 143 3 modulo 143 = 3 mod (11*13) Then he jumps to this: √3 (mod 11) = ± 5 √3 (mod ...
1
vote
1answer
225 views

Sum of a series involving modulus operator

I'm attempting to work out a problem that involves summing a series of numbers. I know the formula to find each element of the series, but I do not know how to use this to make an equation for the ...
2
votes
3answers
143 views

Modular Arithmetic with Powers and Large Numbers

I have a question similar to the following: Evaluate $8767^{2123} \mod 15$. So I got $(8767^{11})^{193}$ $(8767^1*8767^{10})^{193}$ $(8767^1*(8767^3 *8767^4))^{193} \mod 15$ Now I haven't ...