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

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
136 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'...
2
votes
2answers
134 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}}\...
-5
votes
1answer
39 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
1answer
59 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 ...
6
votes
0answers
51 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
2answers
46 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
71 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
40 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
13 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
146 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
191 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
38 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
29 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
49 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$ [on hold]

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
91 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
138 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
45 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 ...
-4
votes
1answer
47 views

How to prove equivalencies for any n? [closed]

The specific problem im trying to solve is the following: $ 441n^{43} + 374n^{35} + 283n^{23} = 0$ mod $55$ is true for all $n$ but im not sure how to prove that. Any leads on how to start would be ...
0
votes
1answer
18 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
47 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
436 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?
0
votes
3answers
43 views

Prove $a \equiv b \pmod{c} \implies a^n \equiv b^n \pmod{c}$.

Prove $a \equiv b \pmod{c} \implies a^n \equiv b^n \pmod{c}$. Here is my proof, which I'm slightly doubtful I've done correctly: Suppose $a \equiv b \pmod{c}$ and $d \equiv e \pmod{c}$ We have: $...
6
votes
1answer
53 views

Why can we exchange numbers when working with modulo expressions?

Please excuse me if the answer is obvious because I'm a beginner. Why can we exchange numbers when working with modulo expressions? For example: $$4^2 \equiv (-1)^2 \pmod{5}$$ You may say the ...
-3
votes
2answers
45 views

Show that the congruence $3x^2 \equiv 12 \pmod{12}$ has a solution, or not [on hold]

Someone know Quadratic residues ? Below: Show that the congruence $3x^2 \equiv 12 \pmod{12}$ has a solution, or not.
2
votes
3answers
327 views

Prove: $a\equiv b\pmod{n} \implies \gcd(a,n)=\gcd(b,n)$ [duplicate]

Proof: If $a\equiv b\pmod{n}$, then $n$ divides $a-b$. So $a-b=ni$ for some integer $i$. Then, $b=ni-a$. Since $\gcd(a,n)$ divides both $a$ and $n$, it also divides $b$. Similarly, $a=ni+b$, and since ...
4
votes
1answer
35 views

Does there exist a general technique for solving systems of multivariable linear congruences

I'm aware for coprime moduli we have the CRT for solving the problem $$ \begin{matrix} a_0 x \equiv b_0 \mod m_0 \\ a_1 x \equiv b_1 \mod m_1 \\ \vdots \\ a_n x \equiv b_n \mod m_n \end{matrix} $$ ...
-1
votes
2answers
1k 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$?
2
votes
1answer
36 views

Division in modular arithmetic

Let $p$ be an odd prime. Given that $a\equiv b \pmod p$ and $c \equiv d \pmod p$, such that none of $a,b,c,d$ is a multiple of $p$. Under what conditions, $\frac{a}{c} \equiv \frac{b}{d} \pmod p$.
5
votes
2answers
100 views

Why does this pattern occur when using modular arithmetic against set of prime numbers?

I have been recently playing around with number theory and going through the project Euler problems. So I am very new to a lot of these things. I apologize for not knowing how to look up my answer. ...
0
votes
3answers
38 views

Using Fermat's Little Theorem to compute vast numbers

I was given a how problem set with the following problems to solve (I'm allowed to use a calculator for all operations excluding exponentiation): $3^{23} + 3 ≡ 5^{37} − 4 \pmod 7$ $1,000,001^{999,...
1
vote
1answer
26 views

If $d\mid n$, element of $(\mathbb{Z}/n\mathbb{Z})^*$ of highest order is also element of $(\mathbb{Z}/d\mathbb{Z})^*$ of highest order

I am not entirely sure if the following lemma is true, but after running a code to check, for smaller values of $n$, it holds. Can someone outline the proof or give a counterexample for it. Lemma: ...