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
1answer
45 views

How many solutions does $x^2 = 1$ have in $\mathbb{Z}/m\mathbb{Z}$ in general?

As the title suggests, how many solutions does $x^2 = 1$ have in $\mathbb{Z}/m\mathbb{Z}$ in general?
2
votes
0answers
31 views
12
votes
1answer
89 views
+100

Are there infinitely many primes $n$ such that $\mathbb{Z}_n^*$ is generated by $\{ -1,2 \}$?

Let $n$ a prime, and let $\mathbb{Z}_n$ denote the integers modulo $n$. Let $\mathbb{Z}^*_n$ denote the multiplicative group of $\mathbb{Z}_n$ Are there infinitely many $n$ such that $\mathbb{Z}^*_n$ ...
1
vote
1answer
20 views

Proving $133|a^{18}-b^{18}$ if $\gcd(a,133)=\gcd(b,133)=1$.

If $\gcd(a,133)=\gcd(b,133)=1$ then prove that $133|a^{18}-b^{18}$. Using Fermat theorem: $a^{132} \equiv 1\mod\ 133$ and $b^{132} \equiv 1\mod\ 133$, so $a^{132} \equiv b^{132}\mod\ 133$. What ...
2
votes
2answers
62 views

Show that, of any set of $2^{n+1}-1$ positive integers numbers is possible choose $2^{n}$ elements such that their sum is divisible by $2^{n}$.

Show that, of any set of $2^{n+1}-1$ positive integers numbers is possible choose $2^{n}$ elements such that their sum is divisible by $2^{n}$. My approach: Let $a_1,a_2,a_3,\ldots,a_{2^{n+1}-1}$ ...
1
vote
3answers
53 views

Why is $15m=0\pmod {18}$ equivalent to $3m=0 \pmod {18}$?

$m$ is some natural number. Why is $15m=0\pmod {18}$ equivalent to $3m=0 \pmod {18}$? This is my question basically. I don't understand why that's true.
-3
votes
2answers
21 views

Prove that $x \pmod n = 0$ if $x \pmod n = (k*x) \pmod n $ and $ k \ne n$

I need a quick formal proof for : Prove that $x \pmod n = 0$ if $x \pmod n = (k*x) \pmod n $ and $ k \ne n$ Thanks
1
vote
1answer
27 views

How would I solve $n(a) := 3 1 7 2 a 6 3 7 5$ with $9|n(a)$?

$n(a) := 3 1 7 2 a 6 3 7 5$ What value needs a to be so that $9|n(a)$? Is there a way to solve this fast? My initial idea was to write it as a sum like $5 + 7 * ...
1
vote
6answers
105 views

Why is $10^k - 1$ divisible by $9$?

I know it is obvious that $10^k-1$ will always be divisible by $9$ for some integer $k$, but I am curious how to actually prove this. $$10^k - 1 \equiv 0 \bmod 9$$ $$10^k \equiv 1 \bmod 9$$ ... and ...
-5
votes
1answer
43 views

Why does the modulo affect other terms in the equation? [on hold]

i just want to ask if why does the modulo affect the other terms in an eqution? Why does the 4th equation has to be multiplied by $a^2$? Then as the modulo becomes $n≡1(mod3)$ in the 5th eq. then the ...
0
votes
2answers
68 views

For all $x$ , $x^2 \equiv 0$ or $1$ or $4 \mod 7$

My textbook makes the following claim For any $x$ , $x^2 \equiv 0$ or $1$ or $4 \mod 7$ I can't see how this true though. $3^2 \equiv 4^2 \equiv 2 \mod 7$ so this obviously doesn't fall into ...
1
vote
2answers
22 views

order of an element in a modulo group under multiplication

Suppose $G$ is the group $ℤ_{37}^\times$ under multiplication. Then is there a way that I can prove the order of the element $2$ in $G$ is $36$ without finding all the powers of $2$ until I get unity?...
1
vote
1answer
25 views

Inverse modulo certain numbers.

Let $b,n$ be given positive integers. I would like to give some formula for the multiplicative inverse $a^*$ of a positive integer $a$ to a modulo of the form $4ab-n$, where $(a,n)=1$, i.e. $$ aa^*\...
-2
votes
0answers
21 views

Modular Arithmetic Division

On this website: http://ptrow.com/perl/calculator.pl when I enter a = -19 , b = 7 using (a/b) and mod 27 the answer comes out to be 5. however when i type "what i assume to be the formula for this ...
4
votes
2answers
288 views

Periodicity in strings

It is known that a string $s$ is actually made up of repetitions of another string $s_1$ of length $L_1$. Also $s$ can be thought of as made up of repetitions of another string $s_2$ of length $L_2$....
1
vote
3answers
137 views

If $n$ is an integer then $\gcd(2n+3,3n-2)=1\text{ or ?} $

There are two possible Gcd's for integers of the form, $2n+3$ and $3n-2$ I know the gcd is $1$ if I take the equation modulo $2$. However if I take the equation modulo $3$ I get, $2n$ and $-2$. ...
2
votes
2answers
65 views

How is this a field?

From Stephen Abbott's - understanding analysis there is a section in the text which says: "The finite set $\{0,1,2,3,4\}$ is a field when addition and multiplication are computed modulo 5." I wasn'...
5
votes
2answers
162 views
+50

Find last 5 significant digits of 2017!

Since there are less powers of $5$ than of $2$ and since $10 = 2 \cdot 5$, I counted the number of zeros in $2017!$: $\left \lfloor{ \frac{2017}{5^1}}\right \rfloor + \left \lfloor{ \frac{2017}{5^2}}\...
1
vote
2answers
50 views

The last eight digits of the binary development of $27^{1986}$

Find the last eight digits of the binary development of $27^{1986}$. We define $v_p(x)$ such that if $v_p(x) = n$, then $p^n \mid x$ but $p^{n+1} \nmid x$. Now we see that if $n \geq 2$ is an ...
2
votes
1answer
81 views

Discrete logarithm modulo powers of a small prime

Is there an efficient way to compute $x$ in $2^x \equiv b \pmod {p^m}$, where $p$ is a small odd prime and $m$ could be a large integer? I know the solution is of the form $x=\phi(p^m) k + y$ for ...
2
votes
3answers
42 views

Why the notation $A\equiv C \pmod B$ instead of $A \text{ mod } B = C$?

Why is, for the modulus operation, the notation $A\equiv C \pmod B$ used instead of $A \text{ mod } B = C$? Or alternatively $\text{mod}(A,B) = C$ or, as in many programming languages, $A\text{ } \% \...
1
vote
0answers
15 views

$i \equiv k \mod p \implies i = k$ if $p$ is prime?

In a particular proof of Fermat's Little Theorem $\big(a^{p} \equiv a \mod p \big)$ in Engel, the following fact is used $i \equiv k \mod p \implies i = k \:$ where $p$ is a prime. I'm not really sure ...
1
vote
9answers
163 views

Last digit on $3^{100}$ [duplicate]

How to find the last digit on $3^{100}$? Is there any proper method to solve such questions without calculator of course?
2
votes
8answers
196 views

Showing that $2^6$ divides $3^{2264}-3^{104}$

Show that $3^{2264}-3^{104}$ is divisible by $2^6$. My attempt: Let $n=2263$. Since $a^{\phi(n)}\equiv 1 \pmod n$ and $$\phi(n)=(31-1)(73-1)=2264 -104$$ we conclude that $3^{2264}-3^{104}$ is ...
1
vote
1answer
41 views

What does ''$p$ of order $10\mod 11$'' mean?

What does ''$p$ of order $10\mod 11$'' mean ? $p$ is a prime, what are then the possibilities for $p$ ?
0
votes
2answers
34 views

Why does an even $x$ imply $y^2=-2 \pmod 8$

I am very new to modular arithmetic, and I encountered the following statement on page 7 of this paper: If $x$ is even then $y^2 \equiv-2\pmod{8}$ The equation in question is $y^2=x^3-2$ I do not ...
2
votes
1answer
39 views

Number of distinct remainders modulo n smaller than Euler's totient function

How come that the number of distinct remainders $a_{k}$ for $g^{k}\equiv a_{k} \mod (n)$ for specific positive $n$ and any positive $g$ and $k=1,2,3...$ is never greater than $\varphi (n)$ (Euler's ...
1
vote
1answer
30 views

If I know N%m , can I compute (N/2)%m? If yes, then how?

This question arrised when I was solving a computer science problem. I don't know the value of N, as N may be very large, but instead I know the value of $N \mod m$. Assume N is divisible by 2. How ...
1
vote
1answer
39 views

Show that if two integers are in this relation then so are their powers

$a\sim b$ is defined as $m$ divides $b-a$, where $m$ is some fixed arbitrary positive integer. Assume $A\sim a$. Show $A^n\sim a^n$ for every positive integer $n$.
1
vote
0answers
50 views

Is there an nth term for this system of modular Equations?

I am interested in the 1st solutions to this set of equations, and wonder if there are any techniques I could use to try and yield an nth term. I'll provide the first few for clarity. General ...
8
votes
1answer
442 views

Conjecture about primes and the factorial: for all primes $p>5$, must there exist a prime $q<p$ such that $q\equiv m!\pmod p$ for some $2<m<p$?

Below $0\notin\mathbb N$. Further corrected conjecture: For all prime numbers $p>5$ there exist a prime number $q<p$ such that $q\equiv m!\!\pmod p$, $2<m<p$. or Given a prime ...
1
vote
2answers
49 views

Prove or disprove that $(A\mathbin\%B)\mathbin\%C = (A\mathbin\%C)\mathbin\%B$ [closed]

Prove or disprove that $(A\mathbin\%B)\mathbin\%C = (A\mathbin\%C)\mathbin\%B$ I am not able how to prove (or disprove by example ) that $(A\mathbin\%B)\mathbin\%C = (A\mathbin\%C)\mathbin\%B$? ...
0
votes
6answers
92 views

Remainder when $5^{5555}$ is divided by $10000$. [duplicate]

Find the remainder when $5^{5555}$ is divided by $10000$. A step by step guide with explanation for a beginner student in modular arithmetic is needed.
2
votes
2answers
69 views

Solve for $b$ in $2^b\bmod11=7$

If I have the equation- $$ 2^b \bmod 11 = 7 $$ How can I solve this to find out what $b$ is? I know $b$ is $7$ but I'd like to know how this is done mathematically rather than guessing.
3
votes
1answer
52 views

How to prove that $\lfloor \frac{n}{2}\rfloor$ = $\lceil \frac{n-1}{2}\rceil$

I'm having a hard time proving that: $$\left \lfloor \frac{n}{2}\right\rfloor = \left\lceil \frac{n-1}{2}\right\rceil$$ I've tried various algebraic manipulations. I've also tried to see if I could ...
0
votes
3answers
38 views

$(a^2) \equiv 1 \pmod{k}$ - we are looking for $a$ - fast way

We have the equation: $(a^2) \equiv 1 \pmod{k}$ We know $k$. It is a quick way to find $a$? (of course other than $1$)
4
votes
5answers
2k views

How do I subtract times?

I have an embarrassingly basic modular arithmetic question. I understand that I can subtract, for example, 1 hour from 10 o'clock to get 9 o'clock, or even 2 hours from 1 o'clock to get 11 o'clock; ...
2
votes
0answers
139 views

Are all theorems usable? [closed]

The (revised) question to answer: Can anyone give an example of a serious proof using this funny (revised) theorem? For any natural number $n$ and prime $p<n-1$ there exist a prime $q$ ...
1
vote
1answer
46 views

Simpler way to compress this exponentiation?

I am trying to find when the following is true: Let $H =(10k)^b \bmod 6(p-1)$ Let $J = 10^{H} \bmod 9p$ For some prime $p > 5$ and large $k,b$. I am trying to find when $J$ is equal to $1$. ...
-1
votes
0answers
20 views

Solving a system of congruences with unkown moduli?

So I have two congruences of the form: n[1]=r[1] mod m and n[2]=r[2] mod (a*m+b) with known n,r,a, and b. Is there a way way to efficiently get (an acceptable) m? Edit: I mean is there any way ...
0
votes
1answer
19 views

Construct a function pertaining to the OEIS sequence A131229 (Numbers congruent to {1,7} mod 10)

OEIS sequence A131229 ("Numbers congruent to {1,7} mod 10") begins $\{1, 7, 11, 17, 21, 27, 31, 37, 41, 47, 51,...\}$. I want a function $f(x)$, specifically such that $f(\frac{1}{2}) =\frac{7}{2}$, ...
0
votes
2answers
22 views

Prove that the modular congruence holds: $b^d$ $=$ $r \pmod n$, $b^{d/q}$ $=$ $x \pmod n$, then $x^q$ $=$ $r \pmod n$.

Prove that if $b^d$ $=$ $r \pmod n$ $b^{d/q}$ $=$ $x \pmod n$, then $x^q$ $=$ $r \pmod n$ for any integers $b$, $n$, $r$, and $q$ (which divides $d$). Or more simply that $b^d$ $=$ $x^q$ $\...
0
votes
1answer
37 views

What is a generalised solution for the Chinese Remainder Theorem?

I recently read that the system of congruences- $$x\equiv a_1\pmod {m_1}$$ $$x\equiv a_2\pmod {m_2}$$$$x\equiv a_3\pmod {m_3}$$...$$x\equiv a_k\pmod {m_k}$$ has a solution given by $$\sum_{i=1}^k\...
0
votes
5answers
10k views

Calculator model with mod function?

I'm wondering does anyone know of a scientific calculator with a mod function? In C# this is shown as follows (just in case there are any other mods that a mathematical non-savant such as myself ...
0
votes
2answers
43 views

why cant i split the modulus?

consider $47^{27}$ congruent to $R \pmod {55}$. since $ 55 = 11\times5$ which are coprime, we can say: $R$ is congruent to $14^{27} \pmod 5 $ and $\pmod {11}$ however $14$ is $-1 \pmod 5$ so $14^{...
12
votes
2answers
278 views

$1989 \mid n^{n^{n^{n}}} - n^{n^{n}}$ for integer $n \ge 3$

Before anyone comments, yes this is kind of a duplicate of Prove that $1989\mid n^{n^{n^{n}}} - n^{n^{n}}$ . The problem that I'm having I don't see the $n=5$ as a counterexample. Also if anyone wants ...
1
vote
1answer
48 views

Prove $\sum_{k=1}^{n} 2^n \text{ mod }k > 2n$ where $n > 1000$

This problem is taken from a Russian textbook of past Olympiads. Its statement looks like this : Given a natural number $n > 1000$ prove that $\sum_{k=1}^{n} 2^n \text{ mod }k > 2n$. ...
0
votes
2answers
65 views

Why does a = b (mod n) iff a - b is divisible by n? [duplicate]

I am specifically asking why the statement $a \equiv b \;(\bmod\; n)$ is equivalent to the statement $a = b + kn$, where k is some positive integer. Why is it that the difference of a and b has to be ...
1
vote
1answer
439 views

How to count soldiers in the army using Chinese Remainder Theorem?

You are a chinese general and you want to count your army. Your estimate is 790,000 - 810,000. Propose the counting to determine the result unambiguously. The soldiers can only count from to 1 to 12. ...
1
vote
4answers
34 views

modular arithmetic help [closed]

$3t_1 \equiv 1 \pmod 5$ $t_1 \equiv 2 \pmod 5$ how can we derive line 2 from line 1?