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

0
votes
1answer
26 views

modular arithmetic with exponents

I'm looking at the solution manual of a book and it lists a solution for (19^3 mod23)^2 mod31 = ((-4)^3 mod23)^2 mod31 = (-64 mod 23)^2 mod31 = 5^2 mod31 = 25 How does it get from (19^3 mod23)^2 ...
3
votes
2answers
60 views

Show that if $R_n$ is prime then $n$ must be prime.

this is an exam practice question: For each positive $n$ define $R_n = \frac{1}{9}(10^n-1) $ (so that in the usual base 10 notation, $R_n = 111,\ldots,1$ where there are n digits). Show ...
1
vote
1answer
33 views

How to find all natural $x$ that make $x^{15} \equiv -1 \mod p$, where $p$ is prime and x<p

For a given prime $p$, how do I find all natural $x$ that make $x^{15} \equiv -1 \mod p$, where $p$ is prime and x < p? The problem is that trying thoroughly every $x < p$ is too inefficient. I ...
4
votes
1answer
137 views

Initial Segments of Modular Arithmetic

Modular arithmetic (MA) has the same axioms as first order Peano arithmetic (PA) except $\forall x(Sx \neq 0)$ is replaced with $\exists x(Sx=0)$. MA is $\omega$-inconsistent and all infinite models ...
4
votes
2answers
368 views

Solving a system of equations using modular arithmetic

I am trying to implement a solver for the game lights out. You have a grid of lights, when you click on one of them the light you clicked and its four neighbours change colour, with the light starting ...
0
votes
1answer
46 views

How to perform division in modular arithmetic on complex exponentials: controversy, bugfix required

I have a complex exponent with prime divisor 7: $e^{\frac{2\pi i \cdot 2}{7}}$ and want to take it to the power 1/3: $e^{\frac{2\pi i \cdot 2}{7 \cdot 3}}$ (I'm learning, how to work with division ...
0
votes
1answer
85 views

“Why are $1/2$ of the non-zero numbers in the mod $p$ system perfect squares and the other half not?”

"Why are $1/2$ of the non-zero numbers in the mod $p$ system perfect squares and the other half not?" This is what led me to realize the part about how half of the non-zero numbers in mod $p$ ...
0
votes
1answer
55 views

What is the identity for ab=2ab (mod 7)?

Using elements 1, 3, 5 write out a Cayley table. The operation for the table is ab = 2ab. For example 5*4= 5*4*2= 40 congruent to 5 (mod 7). What is the identity for this table?
0
votes
2answers
31 views

Smallest integer x s.t. x! congruent to 0 (mod 216)

By guess and check I found x to be 9, but is there a more general way to solve this?
1
vote
2answers
94 views

Find the smallest integer x s.t. x congruent to 1 (mod 1,2,3,4,5,6,7,8,9,10)

Don't really understand this question. If this is asking to find an x for each mod then the answer would be just be x+m...If this is asking to find an x that satisfies all mods, then this cant be ...
1
vote
2answers
85 views

Find integer solutions to linear congruence

Find all integer solutions of $2n \equiv 12 \bmod 19$ So I have re-arranged to: $2x-19y=12$ and by the extended Euclidean Algorithm, I get $$x=1 \ $$ $$y=-9$$ However, this is how far I was able to ...
0
votes
2answers
61 views

Solving $4^{667} ≡ x \pmod{13}$ without Eulers totient theorem or CRT

Does anyone know any efficient ways to solve this without Euler's Totient Theorem or Chinese remainder theorem?
0
votes
1answer
90 views

Modular arithmetic and one-to-one functions

Let $S = \{0, 1, 2, 3, · · · , 99\}$ . For each of the following functions $f : S \rightarrow S$ , determine whether it is one-to-one and onto, by computing its values for all $k ∈ S$: Function 1: ...
0
votes
0answers
25 views

A pair of modular equations

Let $$-pb + qc \equiv s \pmod{p^2}$$ and $$pa - qb \equiv t \pmod{q^2}$$ where $p,q$ are known coprimes with $p^2,pq,q^2>a,b,c>0$ and $s,t$ are known. Is it possible to find $b$? Does the ...
0
votes
1answer
119 views

Computing large exponential modular

My homework question asks me to compute $2^{1386}\mod1387$ without factoring or directly determining whethere 1387 is prime or not; and only use paper, pencil and a basic calculator I used fast ...
2
votes
2answers
285 views

How to compute $2^{\text{some huge power}}$

I have to compute $$2^{p-1} \mod p$$ and show by Fermat's little theorem that $p$ isn't prime. I know what the question is asking but I'm not sure how to reduce the exponent on $2^{p-1}$ to a more ...
2
votes
1answer
55 views

number theory modular arithmrtic system with primes.

For how many distinct primes pqr can we have $$pq \equiv 1 \bmod r$$ $$pr \equiv 1 \bmod q$$ $$rq \equiv 1 \bmod p$$??? I've never arrived at something like this before ( i got here wile doing an ...
3
votes
2answers
99 views

Is there a name for sequences like these?

Starting from an integer value (say $0$ in these cases), I need a sequence of integers to add in a cycle that progress through the integers visiting each exactly once. For example, the most obvious ...
2
votes
0answers
172 views

When quadratic formula $ax^2 + bx +c = 0$ (mod p) is solvable modulo prime p?

I am learning about quadratic congruences and I don't now how to decide, for which a,b,c and p there is a solution of the congruence. It is sufficient if the determinant $\sqrt{b^2-4ac}$ has a ...
0
votes
2answers
266 views

Given remainders, determine smallest possible number of eggs in the basket

I have a question about "Elementary Number Theory - 6th Edition", written by David M.Burton. In page 83 #9, I don't know how to solve it. The problem is, The basket-of-eggs problem is often ...
0
votes
0answers
36 views

How do I prove that $x^2\equiv-1\pmod{p}$ [duplicate]

How do I prove that $x^2\equiv-1\pmod{p}$ iff $p$ is prime at form: $p=4n+1$. I have to use Wilson theroem... (I'm asking this, becuase I didn't understand it from my prev. Q, how it proves that ...
0
votes
1answer
43 views

We had $m$ (odd number)…

What we will get if we divide $2^{\varphi(m)-1}$ at $m$? (The answer should be at $m$...) Thank you! (Mabye it's something that connect to Euler theorem or Fermat Small Theorem).
1
vote
2answers
94 views

Remainder modulo 8

A number is given: $1234513151313653211415515253$ Is there any way to find out the reminder when it divided by 8? What will be happened if I use MOD rules here?
4
votes
1answer
96 views

$m \in \{2,6,42,1806,…\} $ - a problem of sum-of-$m$'th powers modulo $m$

(continuing the work for an answer for a question here in MSE and also in MO) I'm (re-)viewing the function $$ f(m) = \sum_{k=0}^{m-1} k^m $$ considering its residue modulo $m$: $$ r(m) \equiv f(m) ...
2
votes
3answers
170 views

Divisibility problem with modular arithmatic

Here's the question: "When an integer $n$ is divided by 6, the remainder is 5. What are the possible values of the remainder when $9n$ is divided by 8?" I'm not entirely sure how to decipher this ...
2
votes
1answer
322 views

Prove that the mapping $U(16)$ to itself by $x \rightarrow x^3$ is an automorphism

Prove that the mapping $U(16) = \{{1,3,5,7,9,11,13,15}\}$ to itself by $x \rightarrow x^3$ is an automorphism. What about $x \rightarrow x^5$ and $x \rightarrow x^7$? any generalization? So far i ...
3
votes
3answers
75 views

$ 7^{50} \cdot 4^{102} ≡ x \pmod {110} $

The way I would solve this would be: $$ (7^3)^{15} \cdot 7^5 \cdot (4^4)^{25} \cdot 4^2 $$ and take it from there, but I know that this is most likely in an inefficient way. Does anyone have more ...
0
votes
2answers
232 views

Quicker way to solve 10! congruent to x (mod 11)

I am new to modular arithmetic and solving congruences and the way I went about this was to write out $10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot2$. Mulitply numbers until I get a number ...
20
votes
4answers
1k views

Is the number 333,333,333,333,333,333,333,333,334 a perfect square?

I know that if the number is a perfect square then it will be congruent to 0 or 1 (mod 4). Now since the number is even, I know that it is either 0 or 2 (mod 4). How would I go about answering this? ...
1
vote
1answer
54 views

computing the discrete log of $23^x \equiv 102 \pmod {431}$

I've been working on this problem for a while now. Could someone please help me see where I'm going wrong? "Alice and Bob agree to use a Diffie-Hellman key exchange with values p = 431 and primitive ...
-1
votes
1answer
110 views

Is $2^n \mod m \equiv (2^{n/2} \pmod m ) ^ 2 \pmod m$?

I'm trying to write a procedure that solves (2^n - 1) mod 1000000007 for a given n. n can ...
0
votes
1answer
46 views

Antique clock problem: Solve for smallest integer $n \geq0$ in $(h+2n)\bmod {12} = (b + n) \bmod {12},$ where h, b are integers between 12 and 1.

I am not familiar with solving equations of this type. As a background it is actually related to an antique clock in my house that sometimes gets the number of chimes out of synchronization with the ...
14
votes
2answers
390 views

When is $\binom{n}{k}$ divisible by $n$?

Is there any way of determining if $\binom{n}{k} \equiv 0\pmod{n}$. Note that I am aware of the case when $n =p$ a prime. Other than that there does not seem to be any sort of pattern (I checked up ...
0
votes
1answer
59 views

Question about the reduced residue system for a given primorial

It is well known that the number of elements in the reduced residue system for a given primorial $p_k\#$ is divisible by $p_k - 1$. Does it follow that if you divide the elements of a reduced residue ...
6
votes
6answers
453 views

How to efficiently compute $17^{23} (\mod 31)$ by hand?

I could use that $17^{2} \equiv 10 (\mod 31)$ and express $17^{23}$ as $17^{16}.17^{4}.17^{3} = (((17^2)^2)^2)^2.(17^2)^2.17^2.17$ and take advantage of the fact that I can more easily work with ...
1
vote
2answers
83 views

Fermat's Little Theorem and Prime Moduli

I am given two distinct primes $p$ and $q$, where $$m = p*q$$ Also, $$ \begin{cases} r\equiv 1\mod p-1\\ r\equiv 1\mod q-1 \end{cases} $$ I have to show that given an integer a, show that $$a^r ...
0
votes
2answers
46 views

Prove that for every $x \in \mathbb{Z}$ for which $x \geq 3$, if $x \equiv 3 \pmod 4$ then $3^x - 2 \equiv 0 \pmod 5$

Prove that for every $x \in \mathbb{Z} \geq 3$, if $x \equiv 3 \pmod 4$ then $3^x -2 \equiv 0 \pmod 5$. I was trying to use induction: Base case $(x = 3)$: If $3 \equiv 3 \pmod 4$ then $3^3 - 2 ...
0
votes
1answer
57 views

Why do the moduli need to be relatively prime in order to apply the Chinese Remainder Theorem?

Could someone provide a brief explanation or proof of why the moduli need to be relatively prime/coprime in order to apply the Chinese remainder theorem?
0
votes
1answer
58 views

Calculating primitive roots

Wikipedia cleanly demonstrates that $3$ is a primitive root modulo $7$. Here is the table, and my question is how do they calculate the 4th column? It appears that they take the exponent from the ...
0
votes
1answer
61 views

Relatively Prime Mods and CRT

I have to show that the system of congruences $$ \begin{cases} x\equiv a\pmod m\\ x\equiv b\pmod n \end{cases} $$ has solutions for any a,b integers iff $\gcd(m,n)=1$ where m,n are integers. So ...
0
votes
1answer
59 views

for what value(s) of $x$ is $nx$ congruent to $1 \pmod {(n+1)}$

I need to find some fixed integer value for $x$ which satisfies $ nx \equiv 1 \pmod{ n+1} $. This is for a midterm review and I dont really see how this is possible without using $n$ in the formula, ...
1
vote
2answers
70 views

${{p^k}\choose{j}}\equiv 0\pmod{p}$ for $0 < j < p^k$

$${{p^k}\choose{j}}\equiv 0\pmod{p}.\ \ \ \text{for $0 < j < p^k$ and p is prime}$$ I can show this for $k=1$ using the fact that in denominator all numbers are less than $p$. I need hint ...
0
votes
1answer
127 views

Is $2^k = 2013…$ for some $k$? [duplicate]

I'm wondering if some power of $2$ can be written in base $10$ as $2013$ followed by other digits. Formally, does there exist $k,q,r \in \mathbb N$ such that $$2^k=2013 \cdot 10^q+r \,\,\,; ...
5
votes
4answers
120 views

${{p-1}\choose{j}}\equiv(-1)^j \pmod p$ for prime $p$

Can anyone share a link to proof of this? $${{p-1}\choose{j}}\equiv(-1)^j(\text{mod}\ p)$$ for prime $p$.
0
votes
1answer
42 views

Cyclic Allocation, Defining the Worker's Set

Cyclic allocation is a method of assigning $n$ tasks to $p$ workers. The foreman allocates task $k$ to worker $k \mod p$. $$a = k \mod p$$ Now I am interested in how the worker can calculate his ...
0
votes
1answer
49 views

Manually computing a galois field element [duplicate]

$F = GF(2^6)$ modulo the primitive polynomial $h(x) = 1 + x^2 + x^3 + x^5 + x^6$ and $\alpha$ is the class of $x$: $GF(2^6) = \{0,1,\alpha, \alpha^2...\alpha^{62}\}$ How do I manually compute ...
1
vote
1answer
47 views

Order of modular group

Prove $|(\mathbb{Z} / p^e \mathbb{Z} )^{\times}| = p^e - p^{e-1}$ I know it has something to do with the fact that we have $p^e$ elements and we're substracting $p^{e-1}$ multiples of $p$, but I'd ...
1
vote
2answers
95 views

$a^{(p-1)/2} \equiv \pm 1 \pmod p$

Show that if $a$ is any integer not divisible by $p$, then $a^{(p-1)/2}\equiv \pm 1 \pmod p$. I know one wants to use Fermat's Little Theorem which states if $a$ is any integer not divisible by $p$, ...
1
vote
1answer
34 views

How come when $2^{k} | (x-1)(x+1)$ one of the terms is divisible by $2$ and not by $4$ when $k \in \mathbb{N} $ and $3 \leq k$

So I'm reading Knuth's 'Discrete Mathematics' at the moment and there's a paragraph detailing how many solutions are there for $x^{2} \equiv 1 \pmod{p}$. So other cases (when $p$ is an odd prime or ...
0
votes
1answer
38 views

Question about $a \equiv b \pmod{mn} \Leftrightarrow a \equiv b \pmod{m} \wedge a \equiv b \pmod{n}$

So Knuth's 'Discrete Mathematics' states that: $a \equiv b \pmod{mn} \Leftrightarrow a \equiv b \pmod{m} \wedge a \equiv b \pmod{n}$ if $m$ and $n$ are relatively prime. But being a curious human ...