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
2answers
288 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
56 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
1answer
259 views

When is the quadratic congruence $ax^2 + bx +c \equiv 0 \pmod p$ solvable?

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. Is it sufficient if the discrminant $b^2-4ac$ has a solution ...
0
votes
2answers
373 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
38 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
100 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
99 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
173 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
451 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
77 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
273 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 ...
19
votes
4answers
2k 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 ...
1
vote
1answer
77 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
143 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 ...
1
vote
1answer
51 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 ...
16
votes
2answers
426 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
71 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
578 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
92 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
72 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
60 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
73 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
65 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
72 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
141 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
50 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
96 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
39 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 ...
4
votes
2answers
86 views

Smallest such $n \in \mathbb{N}$ that $2^{n} \equiv 1 \pmod{5\cdot 7\cdot 9\cdot 11\cdot 13}$

Can anybody give me a hint about how to find smallest such $n \in \mathbb{N}$ that $2^{n} \equiv 1 \pmod{5\cdot 7\cdot 9\cdot 11\cdot 13}$? I thought that I will find it piece by piece with help ...
1
vote
0answers
26 views

Finding the totient functionlike function for an irrational number like (a+b*sqrt(5)) where a and b are whole numbers mod M where M is a whole number.

I need to find if a value $T$ exists for irrational number of the form $(a+b\cdot \sqrt{5})$ such that $(a+b\cdot \sqrt{5})^T = 1 \pmod M$. Also ,is it possible to find out upper bound for T .
1
vote
1answer
55 views

A curious congruence relation

Find the set of values for n such that $x^n \equiv{x}\mod 10$, where $n, x\in\mathbb{N}$. This question looks like a Fermat's little theorem question but $10$ is not prime. Rather the smallest ...
2
votes
1answer
100 views

Proof using Chinese Remainder Theorem for $n=p_1^{m_1}\cdot p_2^{m_2}\cdots p_k^{m_k}$

I wish to find an expression for the number of solutions $x$ to $x^2\equiv 9 \pmod n$, with $x$ a natural number${}<n$, when $n$ has a factorization $n=p_1^{m_1}\cdot p_2^{m_2}\cdots p_k^{m_k}$ ...
0
votes
1answer
662 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
598 views

What is a perfect square in mod n

I have been stuck with a question on eliptic curves lately. I need to know whether perfect square mod n is different than a normal perfect square. And also is 3 a perfect square in mod 13?
1
vote
1answer
119 views

Prove that there exists only 2 solutions for $x^2 \equiv 9 \pmod {p^k}$, ($p$ an odd prime > 3 and $x$ a natural number < $n$)

It appears that the only two solutions are always $3$ and $p^k-3$, I want to prove this, here has been my approach, I think I am close but just missing something, would really appreciate any help!!! ...
0
votes
1answer
59 views

Prove that for $n=2^k$, $(k \ge 3)$ there are 4 natural numbers less than $n$ that satisfy $b^2 \equiv 9 \pmod n$.

I think I am close to proving this, but just need a bit of help with some gaps in my understanding. I found using a recursive function in a small program that it seemed that for $k \ge 3$, I always ...
2
votes
1answer
103 views

Number of points on $Y^2 = X^3 + A$ over $\mathbb{F}_p$

Let $p\equiv 2\pmod{3}$ be prime and let $A\in\mathbb{F}^{∗}_p$ . Show that the number of points (including the point at infinity) on the curve $Y^2 = X^ 3 + A$ over $\mathbb{F}_ p$ is exactly $p + 1$ ...
0
votes
5answers
5k views

How often in years do calendars repeat with the same day-date combinations (Julian calendar)?

E.g. I'm using this formulas for calculating day of week (Julian calendar): \begin{align} a & = \left\lfloor\frac{14 - \text{month}}{12}\right\rfloor\\ y & = \text{year} + 4800 - a \\ m & ...
3
votes
1answer
51 views

modular arithmetic with large numbers

I am having trouble finding a number where 579^$65$ is congruent to x mod 679 and x has to be less than 676. i did the trick of 2's and got: $579^2$ $\equiv$ 494 mod 679 $494^2$ $\equiv$ 275 mod 679 ...
1
vote
2answers
77 views

modular arithmetic with a very big number

I need to compute $147^{65}\pmod{679}$. I need to get it to be congruent to a number less than $676\pmod{679}$. Anyone who can help? I tried the power of $2$ trick but I couldn't make it work.
0
votes
1answer
52 views

Modular Exponentiation Equivalence Problem

Find the integer $a$ such that $0 \leq a < 113$ and $102^{70} + 1 \equiv a^{37} \bmod{113}$. I started off by using modular exponentiation to realize that the left side of the congruence is ...
2
votes
3answers
65 views

computing $2^{170}+ 3^{63}\pmod {19}, 3^{175} + 2^{73} \pmod {17}$, etc… by hand

I came across several questions like this in the problem section of a book on coding theory & cryptography and I have no idea how to tackle them. There must be a certain trick that allows for ...
0
votes
2answers
129 views

Finding $x$ that make $x^2 ≡ 1 (\mathrm{mod} \ n)$, when $n$ is a composite number

How do I find $x$, $( x > 1)$, that makes $x^2≡1 (\mathrm{mod} \ n)$, for any natural number $n$?