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
0answers
35 views

Pattern involving squares, primes, and remainders

I ran across a really neat pattern, wholly by accident. In advance, my questions are: Has this been discovered before? If so, where can I learn more about it? Why does this pattern work? Now for ...
14
votes
5answers
2k views

How can I tell if a number in base 5 is divisible by 3?

I know of the sum of digits divisible by 3 method, but it seems to not be working for base 5. How can I check if number in base 5 is divisible by 3 without ...
1
vote
1answer
69 views

$ \left\lfloor \dfrac{n-1}{2}\right\rfloor +\left\lfloor \dfrac{n+2}{4}\right\rfloor + \left\lfloor\dfrac{n+4}{4} \right\rfloor =n$

Show that :$$ \forall \in \mathbb{Z}, \left\lfloor \dfrac{n-1}{2}\right\rfloor +\left\lfloor \dfrac{n+2}{4}\right\rfloor + \left\lfloor\dfrac{n+4}{4} \right\rfloor =n$$ Solution provide by book: ...
3
votes
1answer
37 views

Prove that $x^{n}\pmod {(x^{4}+1)}=x^{n \pmod 4}$

Assume $GF(2^k)[x]$ (where $k$ is a fixed natural number) is a ring of polynomials with coefficients in the field $GF(2^k)$. Prove that for every polynomial $x^n$ (where $n \in \mathbb{N}$) from $GF(2^...
3
votes
6answers
147 views

Find the rightmost digit of: $1^n+2^n+3^n+4^n+5^n+6^n+7^n+8^n+9^n$

Find the rightmost digit of: $1^n+2^n+3^n+4^n+5^n+6^n+7^n+8^n+9^n(n$ arbitrary positive integer) First of all I checked a few cases for small $n$'s and in all cases the rightmost digit was $5$, so ...
-1
votes
2answers
36 views

-3 is quadratic residue if and only if $p \equiv 1,7 \pmod {12}$ [closed]

I have to prove that -3 is quadratic residue if and only if $$p \equiv 1,7 \pmod {12}$$ I know one method (with symbol Legendre'a) but I don't get. If someone can explain me I will be happy or give ...
0
votes
2answers
29 views

Prove that g is a primitive root modulo m.

We have natural number $m \ge 2$ which is relatively prime with integer number $g$. Let's assume that for every prime divider $q|\varphi(m) $ we have $$ g^{ \frac{\varphi(m)}{q} } \not\equiv 1 (mod \...
0
votes
0answers
8 views

finding inverse in affine cipher

I am working on an example of Affine cipher, the decryption function is: $$ x=Dk(y)=7^{-1}(y-3) mod 26 $$ I didn't understand how 7 inverse is 15? $$ 7^{-1} = ...
0
votes
1answer
13 views

Maximize a linear equation with a modulo

How can i maximize the function of the type (ax + b) % c where a, b, c are constants and are given while x is a integer variable ? I'm not getting any idea how to start solving such problems.
0
votes
1answer
40 views

Summing (and not summing) to $0\bmod9$

Let $n_0,n_1,n_2\in\{1,2,\dots,8\}$ and consider the sum \begin{align*} S&=\sum_{k=0}^8n_{k\bmod3}\\&=n_0+n_1+n_2+n_0+n_1+n_2+n_0+n_1+n_2. \end{align*} Is there an efficient way to ...
0
votes
1answer
28 views

Need a proof for a modular arithmetic property

From a book I knew something about RSA algorithm .There I found a modular arithmetic property i.e $ (a\bmod n)^d\mod n=a^d\bmod n$ I don't know why this property works .Can anyone give me an ...
1
vote
1answer
25 views

If $h=g^{(p-1)/4}$ show $h^2=-1$

Let $g$ be a generator of the multiplicative group {$1, 2, \cdots, p-1$} and set $h=g^{(p-1)/4}$ where $p$ is a prime with $p\equiv 1\pmod 4)$. I would appreciate help showing $h^2=-1\pmod p$. I ...
0
votes
1answer
30 views

Computing difference in modular arithmetic. [closed]

Is there a meaningful kind of difference "$|a-b|$" in modular arithmetic? For example, in mod $12$, we would like to have $|0-11|= 1$ and $|0-1| = 1$.
2
votes
0answers
29 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$.
0
votes
3answers
56 views

Modular question. Need help please [closed]

Solve the equation $$x^2+6x+10 \equiv 0 \pmod {17}$$
2
votes
3answers
57 views

$a^3+b^3+c^3\equiv{0}\pmod7\implies $ at least one of $a,b$ or $c$ is divisible by $7$

Show that if $a^3+b^3+c^3\equiv{0}\pmod7\implies$ at least one of $a,b$ or $c$ is divisible by $7$. Here it seems Fermat's theorem has no use. We could consider many different cases of remainders of ...
2
votes
2answers
26 views

Mod with a negative number

I know how $\div$ and $\mathrm{mod}$ works but I have come across the following example and I do not understand it: $-117 \pmod {352} = 235$ Shouldn't that be equal to $-117$?
1
vote
2answers
61 views

Prove that if $ p | x^p + y^p $ where $p$ is a prime number greater than $2$, then $p^2 | x^p + y^p$

I was trying to solve the following problem recently: Prove that if $ p | x^p + y^p $ where $p$ is a prime number greater than $2$, then $p^2 | x^p + y^p$. Here $x$ and $y$ are both integers. $a|b$ ...
0
votes
0answers
20 views

Simplify Modulus Argument

I have the following expression (all quantities exact):$$ \left[( 85155.86592 \cdot x + 29.714 ) \cdot \frac{\pi}{180}\right] \mod 2 \cdot \pi, ~~~~~~~~~~~x \in \mathbb{R} $$It turns out that the ...
1
vote
3answers
43 views

Find the element in $\mathbb{Z}/143\mathbb{Z}$ whose image is $(\overline{10},\overline{11})$ under the Chinese remainder theorem

Find the element in $\mathbb{Z}/143\mathbb{Z}$ whose image is $(\overline{10},\overline{11})$ in $\mathbb{Z}/11\mathbb{Z} \times \mathbb{Z}/13\mathbb{Z}$ under the Chinese remainder theorem So I ...
0
votes
3answers
45 views

Modular Arithmetic: Computing last digit of $206746^{20}$ [duplicate]

I have been given the number: ${206746}^{20 }$and the problem wants me to compute the last digit using modular arithmetic. How would I go about this? I know that since the ones digit is 6, no matter ...
2
votes
1answer
23 views

matrix inverse with modular entries?

So I am dealing with a square $nxn$ matrix where the entries are all integers taken modulo $m$, we can assume $m$ to be a prime. Can we make sense of an inverse of such a matrix? Assuming of course ...
0
votes
2answers
60 views

If $b^2 \equiv 1 \pmod 3$, is it possible to have $\sigma(b^2) \equiv b^2 \pmod 3$?

The title says it all. Let $\sigma(N)$ denote the sum of the divisors of the positive integer $N$. To paraphrase my question: If $3 \mid \left(b^2 - 1\right)$, is it possible to have $3 \mid \...
0
votes
1answer
20 views

System of congruences of 2 unknowns

Given constants $A, B, C, D$, and unknowns $x, m$, how would I go about solving a system such as this: $$A\equiv x B\mod m$$ $$C\equiv x D\mod m$$ I'm certain there is a very simple equivalent form of ...
2
votes
5answers
68 views

Let $n \in \mathbb{N}$. Proving that $13$ divides $(4^{2n+1} + 3^{n+2})$

Let $n \in \mathbb{N}$. Prove that $13 \mid (4^{2n+1} + 3^{n+2} ). $ Attempt: I wanted to show that $(4^{2n+1} + 3^{n+2} ) \mod 13 = 0. $ For the first term, I have $4^{2n+1} \mod 13 = (4^{2n} \cdot ...
1
vote
2answers
73 views

If $a \in A$ and $b \in B$ then $2a \in B$ and $2b \in A$ and $(a+b)^{2014}\in C$ [closed]

Below are questions that it think I know how to do but im not $100\%$ sure. $(i)$ asks if $a$ is odd so $a=k+1$, then prove $2a$ is even so $2a = 2k+2.$ The second and third differ a little am I ...
0
votes
1answer
23 views

Quadratic modular equation

Let $n = pq$, where $p$ and $q$ are prime numbers and $a = n + 1 - \varphi(n)$. Then what are the roots of the equation: $$x^2 + ax + n = 0 \ (mod \ n)$$ Any help with this ? Thanks in advance !
6
votes
2answers
82 views

Number theory: Solving $2^n-1\equiv0\pmod{n+1}$.

If $n$ satisfies the congruence $$2^n-1\equiv0\pmod{n+1},$$ then what is $n$? Or if you can't know what $n$ is, then what can be said about $n$? Thank you in advance.
0
votes
1answer
13 views

Modulus of numbers for negative divisors

How does the Google calculator or the Wolfram calculator calculate the modulus of the numbers with negative divisors? For example: -4 % -3 = -1 and 4 % -3 = -2 The same topic has been mentioned ...
0
votes
0answers
15 views

System of 2 modular equations

I don't know where I am making mistake in my calculations. Please verify: $ x \equiv 569^{679} \mod 851 $ Note that $851 = 23.37, 679 = 12.56 + 7 = 11.61 + 8 $ and by Fermat's Little Theorem $569^{...
2
votes
2answers
47 views

Evaluating the remainder of $652^{679} : 851$

Evaluating the remainder of $652^{679} : 851$ I'm having trouble solving this problem, specially because I saw congruence properties a long time ago, but this is what I tried: $652^{679}={652^{7}}^{...
1
vote
2answers
29 views

Find a positive integer $x$ such that $0<x\leq38$ and $14^{36}\equiv x\pmod{38}$

Find a positive integer $x$ such that $0<x\leq38$ and $$14^{36}\equiv x\pmod{38}$$ This is what I've come up with so far: $$14^{36}\equiv x\pmod{38} \iff 14^{36}\equiv x\pmod{19} \, \land 14^{36}\...
0
votes
2answers
22 views

prove $a \equiv b \pmod{p_1}$ and $a \equiv b \pmod{p_2} \Rightarrow a \equiv b \pmod{p_1\times p_2}$

I am following a proof of an RSA algorithm and the proof states the following: $p_1$ and $p_2$ are distinct primes, $a \equiv b \pmod{p_1}$ and $a \equiv b \pmod{p_2} \Rightarrow a \equiv b \pmod{p_1\...
1
vote
1answer
39 views

Find all integers $0\leq x<19$ such that $x^{19}+x^{38}\equiv 2\pmod{19}$

Find all integers $0\leq x<19$ such that $$x^{19}+x^{38}\equiv 2\pmod{19}$$ I think I'm supposed to use Fermat's Little Theorem here and I'm aware that this says that if $p$ is a prime and $a$ is ...
5
votes
4answers
100 views

Find the last two digits of $2^{2156789}$

Find the last two digits of $2^{2156789}$. My try: As $2156789 = 4* 539197 + 1$ The unit digit of $2^{2156789}$ is similar to the unit digit of $2^{4n+1}$ which is equal to 2. But I'm unable to find ...
3
votes
1answer
25 views

basic modulus question

So if so $a \equiv b \pmod{n}$, which should be read as "$a$ is congruent to $b$ modulo $n$" which from what I understand is something among the lines of "$a$ is the remainder when $b$ is divided by $...
0
votes
1answer
47 views

Does $x^2+1$ have roots in $Z_{103}[x]$? [duplicate]

I am trying to figure out if $x^2+1$ has any roots in $Z_{103}[x]$, but I don't have any idea of how I should find the answer. Any help would be much appreciated. Thank you.
1
vote
1answer
32 views

Find two natural numbers $m$ and $n$ such that the order of $n$ modulu $m$ equal to $2012$

Find two natural numbers $m$ and $n$ such that $\gamma_m(n)=2012$ My atempt: $$\varphi(n)\mid2012$$ $$\Longrightarrow \varphi(n)\in\{1,2,4,503,1006,2012\}$$ I am stuck here
0
votes
0answers
19 views

Solving $ b^k= a~ mod~ 2^n$

I wonder how given $a \in \mathbb{Z}$, $ k,n \in \mathbb{Z}_{\ge1}~ k~odd$, $~~ b^k= a~ mod~ 2^n$ is solvable using Newton-Iteration. I tought of using $X^k-a$ as $f(x)$ and using a validation Ring. ...
0
votes
1answer
12 views

Carry of multiplication in base k

I'm trying to implement a library of big numbers and I'm stuck with multiplication. The issue is not in finding a good algorithm (Karastuba will be fine), but in a way to compute carry of two numbers ...
0
votes
1answer
29 views

Find Integer Solution for $(g^x) \bmod p = 1$

Consider the following: $(g^x) \bmod p = 1$, where $p$ is a prime; $g$ is a primitive root modulo $p$. Is it possible to find the integer solution for any $p$, $g$?
1
vote
1answer
21 views

Relation between powers of inverse modulo n.

Recently, I was studying enchanced euclidean algorithm. I am wondering if there is some way to calculate inverse of $a^2$ (and higher powers) modulo $n$, knowing inverse of $a$ modulo $n$. For example:...
3
votes
2answers
42 views

The order of $33\pmod{83}$

Find $\gamma_{83}(33)$ My attempt: stupid approach: $33^1\equiv 33 \pmod{83}$ $33^2\equiv 10 \pmod{83}$ $33^3\equiv 81 \pmod{83}$ $33^4\equiv 17 \pmod{83}$ $33^5\equiv 63 \pmod{83}$ $\vdots$ ...
1
vote
2answers
12 views

the connection between $\gamma_m(a)$ and $\gamma_m(b)$ when $a\cdot b\equiv 1\pmod m$

show the connection between the order of $a$ $\gamma_m(a)$ and the order of $b$ $\gamma_m(b)$ when $$a\cdot b\equiv 1\pmod m$$ I took $a=5$ and $b=4$ $$5\cdot 4\equiv 1\pmod{19}$$ $$\...
1
vote
3answers
56 views

Solve $636^{369}\equiv x\pmod{126}$

Solve $$636^{369}\equiv x\pmod{126}$$ My attempt: $$126=2\times 3^2 \times 7$$ $$\varphi(126)=\varphi(2)\times \varphi(3^2)\times \varphi(7)=36$$ $$\color{gray}{636=6\pmod{126}}$$ $$6^{369}\...
1
vote
0answers
26 views

Calculate modulo expression

How does one evaluate the expression; $$5\times52^{366} \mod367^1$$ I can infer from the exercise solutions that $52^{366} ≡ 1 \mod 367$, but why?
1
vote
2answers
73 views

How to find remainder of a very large number when divisor is 17?

How to find the remainder when $2^{2015}$ is divided by $17$? I tried dividing $2,4,8,16$ etc by $17$ and finding the remainder in each case to form some particular sequence but failed can someone ...
1
vote
2answers
34 views

Application of Fermat's Little Theorem/Fermat Euler Theorem

Find an integer $x$ with $0\leq x \leq73$ such that $$2^{75}\equiv x \pmod{74}$$ I think I'm supposed to be using either Fermat's Little Theorem or the Fermat-Euler theorem here but I don't think I ...
0
votes
1answer
32 views

On exponent mod $2p$.

Assume $p$ is a prime. Assume $g$ is primitive root for both $\Bbb Z_p$ and $\Bbb Z_{2p}$. We know in discrete logarithm problem $z$ is unique $\bmod(p-1)$ in $g^z=h\bmod p$. Is it true that $z'$ ...
0
votes
1answer
88 views

Equality simplification — have I done it correctly?

I previously posted this equality and got some nice feedback. This is my final equality to prove Legendre's, Brocard's, Andrica's, and Oppermann's Conjectures. The first equality was to determine if ...