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
2answers
249 views

congruence proof

I am looking into congruences for school and I have trouble understanding on how to prove this (i understand modules, congruences but don't know how to prove it). I need to prove that if this ...
2
votes
1answer
74 views

Modulo equation : $\frac{n^{k+1}-1}{n-1} \equiv a{\pmod p}$

Can we have directly answer for this question : $$\frac{n^{k+1}-1}{n-1} \equiv a{\pmod p}$$ (p is a prime and k,n is a fixed number) My question is : with fixed number n, k and p, can we know value ...
3
votes
1answer
247 views

Solvability of $x^q=2\mod p$

I've been discussing a problem recently Let $p, q$ be primes. If $x^q\equiv2\pmod p$ has no solution then $p\equiv1\pmod q.$ This is not a bi-equivalence (though it is "nearly" one): there are 811 ...
2
votes
4answers
182 views

How many solutions does equation $6x=14 \bmod 35$ in $\mathbb{Z}/35\mathbb{Z}$ have?

Yes, this is a homework problem. And no, I'm not asking for the answer to this. I just want to understand how to tackle this type of problem. What are the steps towards finding the solutions? My ...
0
votes
5answers
3k views

How is 3 modulo 5 = 3

Just tried googling but couldn't find any example, but how 3 % 5 = 3 Googled it
0
votes
1answer
51 views

How can I create a function that simulates a “linked list”?

If I have: { 0, 1, 2, 3, 4, 5, 6 } How can I make a function that will return the number of steps to a target element, in one direction? To clarify, let the target be 2... Say that x = 5, and I ...
1
vote
0answers
248 views

Modular multiplicative inverse and coprime numbers needed.

I have a 64 bit algorithm that uses modular multiplicative inverse and coprime numbers, and I need to convert it to 32 bit. This math is not my area, and I cannot find an online calculator, so I hope ...
2
votes
1answer
113 views

Problem with Modulus and division

Suppose I want to compute $(a_1 + a_2 + ... + a_n) \mod m $. For very large values of $a_i$, I can take modulo after every operation: $ [(a_1 \mod m) + (a_2 \mod m) + ... + a_n \mod m] \mod m$ (I ...
1
vote
3answers
3k views

Find the multiplicative inverse of 23 in Z26

I have no number theory training, but I did many google reading prior coming here. There are so many ways to solve this problem but I am lost. How would you find the answer to the question Find the ...
1
vote
2answers
193 views

Function with a Modular Inverse

For a combinatorics problem I have a function, $h(x)$ that is always divisible by five, but it is calculated in pieces, e.g. $h(1) = 43 + 7$. The final function that I need is $f(x) = (h(x) / 5) ...
1
vote
1answer
285 views

How to remove the denominator?

I have the following expression for $n>3$: $$\frac{5\cdot(n-1)\cdot[8\cdot\operatorname{Luc}(n) + 5\cdot\operatorname{Luc}(n-1)] + [4\cdot\operatorname{Luc}(n-1) - ...
1
vote
1answer
96 views

Solving $a + b x = c y$ in the integer domain for general $a$

I have the following equation: $\frac{a + b x}{c} \in \mathbb{N}$ where $a,b,c,x \in \mathbb{N}$. and I want to find all x that satisfy these requirements. This should be the same as: $a + b x = c ...
2
votes
2answers
117 views

What is the fastest or usual way to calculate $(\frac{x-1}{2})^2$ mod $x$ if $x$ is odd?

Because: A) for odd $x$ and $x \equiv 1\pmod {4}$ the upper formula is the same as $x - (x-1)/4$ B) for odd $x$ and $x \equiv 3\pmod {4}$ the upper formula is the same as $(x + 1)/4$ Example A) ...
0
votes
1answer
134 views

Mix of Modulus and Division

While solving problems in SPOJ, I faced cases where I need to take Modulus of Big numbers like Fibonacci with 10^9 + 7 ( say MOD ). Now, consider the following case : (Fib(n) + Fib(6*n-1)) / ...
2
votes
4answers
163 views

How to implement modular division?

I want to calculate do calculate $\frac{a}{b} \pmod{P}$ where $a$ is an integer less $P$ and $P$ is a large prime, $b=5$, a fixed integer. How can I implement it? Any algorithm which will work well?
4
votes
2answers
124 views

What's the answer of (10+13) ≡?

As to Modulus operation I only have seen this form: (x + y) mod z ≡ K So I can't understand the question, by the way the answers are : ...
1
vote
1answer
500 views

Modulo of (Power of 2 divided by a number)

I wanted to calculate the power of $2$ raised to a number $a$, divided by another number $b$ and then take the modulo $K$ of this quantity. Meaning, I basically wanted $(2^a/b) \mod K$. Take an ...
2
votes
1answer
96 views

Name of this division property

Let us take two integers, $a$ and $b$. Let us then take $\lfloor a / b\rfloor = c$ and $a \bmod b = d$. Obviously, it follows that $a = bc + d$. Our professor claimed that this was called the ...
1
vote
3answers
237 views

How many distinct degree 7 polynomials are there over the modular arithmeic modulo 7?

If it's infinite, is it countable or uncountable infinite? I am a newbie to this topic... I don't know what modular arithmetic for polynomials means. Can someone please give me a link where I can ...
6
votes
5answers
281 views

How to solve $100x +19 =0 \pmod{23}$

How to solve $100x +19 =0 \pmod{23}$, which is $100x=-19 \pmod{23}$ ? In general I want to know how to solve $ax=b \pmod{c}$.
1
vote
0answers
62 views

Modular simple equation

Let's say I have three known numbers : $a$, $b$ and $m$. I want to find the smallest $x$ so that $a.x \equiv b\ (mod\ m)$ (the product of $a$ and $b$ is congruent to $b$ modulo $m$). In the cases ...
12
votes
2answers
352 views

A puzzle with powers and tetration mod n

A friend recently asked me if I could solve these three problems: (a) Prove that the sequence $ 1^1, 2^2, 3^3, \dots \pmod{3}$ in other words $\{n^n \pmod{3} \}$ is periodic, and find the length of ...
0
votes
1answer
101 views

$\mathbb{Z}/n\mathbb{Z}[T]$ and zero divisors

I read the following in wiki, but I can't understand what is meant by "divisor" there. Notice that $(\mathbb{Z}/2\mathbb{Z})[T]/(T^{2}+1)$ is not a field since it admits a zero divisor ...
2
votes
0answers
32 views

Solving $key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$ with High limits

I was solving this equation:- $$key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$$ Given $$ 1,000,000,000 < a, n, m \; < 5,000,000,000 $$ $$ a, m \; are \;coprime $$ I solved it bruteforcely but it ...
1
vote
1answer
374 views

Modular Multiplicative Inverse & Modular Exponentiation Equation

I was solving a problem containing that equation. $$key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$$ Given: $1 \le a \le 2,000,000,000$ $0 \le n \le 2,000,000,000$ $2 \le m \le 2,000,000,000$ $a$ and $m$ ...
1
vote
1answer
645 views

How to use Fermat's theorem in congruence problems

Two days ago I asked about how to solve questions of the type: Find last digit of $27^{27^{26}}$. or Find the remainder when $27^{45}$ is divided by $7$, using congruences. I ...
3
votes
1answer
329 views

Calculating the residue of power towers

I want to calculate the residue of a power tower. How do I do that? For example, I want to know the answer to this: $$2 \uparrow\uparrow 10 \pmod{10^9}$$
6
votes
2answers
452 views

Find all linearly dependent subsets of this set of vectors

I have vectors in such form (1 1 1 0 1 0) (0 0 1 0 0 0) (1 0 0 0 0 0) (0 0 0 1 0 0) (1 1 0 0 1 0) (0 0 1 1 0 0) (1 0 1 1 0 0) I need to find all linear ...
5
votes
5answers
229 views

Proving that $2^{2^n} + 5$ is always composite by working modulo $3$

By working modulo 3, prove that $2^{2^n} + 5$ is always composite for every positive integer n. No need for a formal proof by induction, just the basic idea will be great.
3
votes
4answers
112 views

Trouble relating the two definitions of $(\mathbb Z/n\mathbb Z)^\times$

I am having trouble relating the two definitions of $(\mathbb Z/n\mathbb Z)^\times$, the collection of residue classes having a multiplicative inverse in $(\mathbb Z/n\mathbb Z)$; and apparently, ...
2
votes
2answers
92 views

Counting the number of matrices which cause collision

Let $m,n \in \mathbb{N}$, and $q$ be a prime number. Let $\mathbf{A} \in \mathbb{Z}^{m \times n}_q$ be a matrix. In the following, assume that all additions and multiplications are performed modulo ...
4
votes
2answers
580 views

Legendre symbol, second supplementary law

$$\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$$ how did they get the exponent. May be from Gauss lemma, but how. Suppose we have a = 2 and p = 11. Then n = 3 (6,8,10), but not $$15 = (11^2-1)/8$$ n ...
1
vote
1answer
388 views

Modulus Distributing Over Multiplication?

Given positive integers a,b,c and k: Define a function $M: \mathbb{Z^2} \rightarrow \mathbb{Z}$ as $$M(x,y) = (x \bmod y)$$ i.e. the remainder of integer division The following is always true: ...
38
votes
14answers
2k views

'Linux' math program with interactive terminal?

Are there any open source math programs out there that have an interactive terminal and that work on linux? So for example you could enter two matrices and specify an operation such as multiply and ...
0
votes
2answers
132 views

$k$ hands in $n$'s hair

Moderator Message: this question is from an ongoing competition. Define a prime $p$ as having $k$ hands in $n$'s hair if $p^k|n$ and $n|2^n+1$ . Does there exist an integer $n$ with $2012$ hands ...
1
vote
0answers
162 views

Lucas' theorem Consequence

Lucas' theorem consequence $$\binom {m}{n}=\ \prod_{i=0}^k\;\ \binom {m_i}{n_i} \pmod{p},$$ $$m=m_k\;p^k+m_{k-1}\;p^{k-1}+\cdots +m_1\; p+m_0,$$ $$n=n_k\;p^k+n_{k-1}\;p^{k-1}+\cdots +n_1\;p+n_0$$ ...
2
votes
2answers
125 views

How many elements $a \in \Bbb{Z}_N$ such that $ax \equiv y \mod N$

Consider the ring $\Bbb{Z}_N$ of arithmetic modulo $N$: $\{0,1,2, \ldots ,N-1\}.$ Given $x,y \in \Bbb{Z}_N,$ how many of the elements of $\Bbb{Z}_N$ when multiplied with $x \pmod{N}$ result in $y$? ...
3
votes
9answers
204 views

If both $a$ and $b$ $\not \equiv 0 \pmod{p}$ then $ab \not\equiv 0 \pmod{p}$

Any help with this proof would be great. Not even sure where to begin. I'm pretty much a total newbie. If $a$ is not congruent to $0 \pmod{p}$ and $b$ is not congruent to $0 \pmod{p},$ where $p$ ...
1
vote
3answers
101 views

How to show that $h(x^p) \equiv h(x)^p \pmod{p}$? [duplicate]

Possible Duplicate: Why $g(x^{p})=(g(x))^{p}$ in the reduction mod $p$? Let $h(x) \in \mathbb{Z}[x]$ and $p$ be a prime. We know that for any integer $\alpha$ we have that $\alpha^p \equiv ...
2
votes
0answers
192 views

$a^{(b^c)} \mod m$ where $c$ can be very very large

I am trying to solve the following problem. I need to find the value of $$ a^{(b^x)} \bmod m $$ where $a,b$ are integers and $$ x = \pmatrix{n\\0}^2 + \pmatrix{n\\1}^2 + ... + \pmatrix{n\\n}^2 ...
0
votes
1answer
60 views

Confusion in the answers given by mathematica

When I typed in 6^-1 mod 49 in Wolfram|Alpha, it gave me an answer of 41. Link here If I type the same thing as (1/6) mod 49 , I don't see 41 any more. Why is this happening ?Link here A ...
1
vote
1answer
536 views

Solving a polynomial modulo an integer

Say I have a polynomial $F$ of degree $n$ with coefficients in $Z_m$ and I wish to find $x$ such that $F(x)=0$ (mod $m$). For instance if $F(x)=x^{2}-a$ the solution would be the modulo $m$ squareroot ...
-2
votes
3answers
293 views

$a/b\bmod{m}$ when $m$ is not a prime

I need to find $(a/b) \bmod m$ where $$m= 500000002$$ (hence $$m = 148721 \times 41 \times 41 \times 2\qquad\text{(prime factorization)}$$ basically I need to find $a_n\binom{2n}{n}$, which satisfies ...
0
votes
2answers
94 views

Prove or Disprove $xa \equiv 1 \pmod{ n}$

If $a\in\mathbb{Z}, n\in\mathbb{N}$, then the equation $xa\equiv1\pmod {n}$ has a solution for some $x\in\mathbb{Z}$. I'm not quite sure where to start. I know that $n|(xa-1)$, so $ns=xa-1$ for some ...
1
vote
2answers
174 views

Find the remainder in the following case where there's a infinite power tower of $7$.

What is the remainder when $$7^{7^{7^{7^{.^{.^{.^{\infty}}}}}}}$$ is divided by 13? I'm getting $6$. Is it correct?
2
votes
4answers
82 views

Turn fractions into $\mathbb Z_7$ elements

I had to perform a division between two polinomials $2x^2+3x+4$ and $3x+4$, my book suggests to do this operation without worrying about the modulo. So my result is ...
0
votes
1answer
65 views

System of congruential equations

I read this question about breaking a LCG, but I can't understand how to solve the system of 2 equations given 3 sequential outputs. The system should be ...
1
vote
2answers
100 views

How to solve such congruences? [duplicate]

Possible Duplicate: HCF/LCM problem Given some positive integers $a_i, a_{i+1},\dots,a_n$ we need to find as large as possible number $X$ such that $a_i \pmod x = a_{i+1} \pmod x = \dots = ...
0
votes
2answers
56 views

Security of a particular cryptosystem

I recently came across this problem, and while I'm fairly certain the solution is not too 'conceptually-challenging', I've been stumped at finding the right trick/manipulation to make any solution ...
2
votes
1answer
357 views

Explain Carmichael's Function To A Novice

I understand that the Carmichael Function (I'm going to call C()) is essentially the smallest positive integer m, where $a^m$ is congruent $1 \pmod n$ for all co-primes less than n. 6 makes sense to ...