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
2answers
32 views

How do I solve simultaneous congruence modulo equations

How do I find one value of $x$ in these equations? $$ \begin{cases} x \equiv 3 \pmod{5}\\ x \equiv 4 \pmod{7} \end{cases} $$
0
votes
0answers
9 views

What is the correct term (and symbolic representation) of specific “un-modded” values?

Given $x \in \mathbb{R}$ such that $x \equiv x+k\cdot(b_u-b_l),\,\forall k\in\mathbb{Z}$, are there terms to describe the functions $$f:[b_l, b_u) \to[b_u, b_u+(b_u-b_l)):x\mapsto x+(b_u-b_l)$$ and ...
0
votes
3answers
36 views

Modulo: Calculating without calculator??

Calculate the modulo operations given below (without the usage of a calculator): $101 \times 98 \mod 17 =$ $7^5 \mod 15 =$ $12^8 \mod 7 =$ $3524 \mod 63 =$ $−3524 \mod 63 =$ Ok with calculator ...
0
votes
1answer
6 views

System modular equation. Question.

$$2x \equiv 4 \mod 8 \iff x \equiv 2 \mod 4 $$ And this is true, but is it a true?: $$\begin{cases} 2x \equiv 4 \mod 8 \\ x \equiv 2 \mod 6 \end{cases} $$ $$\iff$$ \begin{cases} x \equiv 2 \mod 4\\ ...
1
vote
6answers
56 views

How to solve this equation if we can't use Chinese remainder theorem.

Let consider: $$\begin{cases}6x \equiv 2 \mod 8\\ 5x \equiv 5\mod 6 \end{cases}$$ We can't use Chinese remainder theorem because $\gcd(8,6) = 2 > 1$ Help me.
0
votes
1answer
17 views

Enciphered Message with linear enciphering function.

My semester tests are coming up and as I was looking through past papers I came across this question. I was missing a lot during the beginning of the year and this was no doubt covered during my ...
2
votes
3answers
43 views

$(a\mod m)/(b\mod m) = (a/b)\mod m$?

b and m are relatively prime (m is prime and $b \in \mathbb Z_m^* $). In truth, I would like to be able to get to the following point (it is a simplified example): $\frac{ab \mod m}{b \mod m} = a ...
1
vote
1answer
28 views

Solutions of $a^{2} - 2b^{2} \equiv 0$ mod $p$

I came across this question in attempting to find $p$ for which $\mathbb{Z}_{p}[\sqrt{2}]$ is a field. Consider the equation: $$a^2 - 2b^2 \equiv 0 \enspace \text{mod p}$$ For which primes $p$ is ...
0
votes
1answer
35 views

Show that x = (66B − 65a) mod 143.

For each natural number $m$ we define $J_m = \{0, 1, . . . , m − 1\}$, the set of all possible residues modulo $m$. Let $x \in J_{143}$. Define $a \equiv x \pmod{11}$, $B \equiv x \pmod{13}$ Show ...
0
votes
2answers
28 views

If $a \equiv b \bmod n$, then $\gcd(a, n)= \gcd(b,n)$ [duplicate]

Again, I have been stuck in a problem of modular arithmetic. Given that $a,b, n \in \mathbb Z $ and $n>0$ and $a \equiv b \bmod n$. Show that $\gcd(a, n)= \gcd(b,n)$.
0
votes
1answer
17 views

proof of a property of modular arithmetic

I have been stuck in a problem related to modular arithmetic. I have tried it using the generalized Euler's formula for $\gcd(a,b)=as+bt$, but have not reached the proof so far. The question is: ...
1
vote
2answers
21 views

Modular arithmetic with (mod 20)

Got a question on my midterm in discrete mathematics and I can' figure out how to approach it: $19^{3701}+1 \equiv 0\ (\textrm{mod}\ 20)$ I was thinking about Fermat´s little theorem, but the 20 is ...
5
votes
2answers
839 views

Why is $20 ≡ 2 \pmod 6\;?$

Could anyone explain to me why $20 ≡ -22 \pmod 6\;?$ At school we did the following method to find $-x \mod n$ by doing: $x \mod n$ (in this case $22 \mod 6 = 4)$ $n - r$ (in this case $6-4 = ...
0
votes
2answers
16 views

Modulo congruence

I have a problem here that I have no idea how to go about solving. It states: Let $n∈Z$ with $n>1$. (a) If $n=2k$ for some odd integer $k$, prove that $k^3≡k \pmod{2n}$. (b) If $n=2k$ for ...
0
votes
0answers
27 views

Finding set of integer pairs for which two integer polynomials intersect

I am wondering if there is a theorem in number theory that addresses the following issue: Suppose we have two polynomials, f and g, with integer coefficients. Is there a general way to find elements ...
-1
votes
1answer
23 views

Show that a·c ≡ b·c (mod m) with a, b, c and m integers with m≥2 does not [3] imply a ≡ b (mod m) [on hold]

I'm working through some practice problems but I am having some trouble understanding this question and was wondering if it'd be possible for someone to help me go over it step by step. Thanks
0
votes
1answer
34 views

Why is the discrete logarithm problem in $(\mathbb{Z}_n,+)$ easy?

I have trouble understanding why the discrete logarithm problem in $(\mathbb{Z}_n,+)$ should be easy: I tried it with the following example: $$a \cdot b \equiv y \pmod {p}$$ If $a=11, b=2$ and ...
3
votes
0answers
36 views
+50

Arithmetic background of this RNG code

I am trying to figure out the mathematical background of the random number generation of an old video game. It does iterations where it updates a 33-bit state consisting of the variables z (32-bit) ...
0
votes
1answer
13 views

Linear Congruences Examples

Solve the following linear congruences: (i) $23x \equiv 16$ mod $107$ (ii) $234x \equiv 20$ mod $366$ (iii) $234x \equiv 6$ mod $366$. I am trying to solve these through the use of the ...
0
votes
0answers
39 views

Prove $2^n \not\equiv 1 \pmod{n}$ for $n>1$ [duplicate]

Prove that $2^n \not\equiv 1 \pmod{n}$ for $n>1$. I'm asking for any advice.
0
votes
0answers
19 views

Modulo-2 arithmetic division

I been recently studying modulo 2 arithmetic addition, subtraction and division. I fully understand addition and subtraction, but I'm still not clear about division. I've made the following ...
1
vote
1answer
21 views

Modular exponentiation twice over

What is a general way to calculate something like $2147089412^{1147068432^{647017654}}$ mod m? It looks like modular exponentiation, but how do you reduce the highest part properly? Note: $m$ is ...
0
votes
0answers
9 views

Let p be a prime number and let n ≥ 1. Show that $\mathbb{F}_p$ contains an element of order n iff p ≡ 1(mod n).

Let p be a prime number and let n ≥ 1. Show that $\mathbb{F}_p$ contains an element of order n iff p ≡ 1(mod n). For the reverse direction, assume $p \equiv 1(mod n). \text{Let } g \in \mathbb{F}_p ...
4
votes
2answers
22 views

$x^2$ $\equiv$ $1$ $\mod{p}$

Can someone provide the proof that $x^2$ $\equiv$ $1$ $\mod{p}$ iff $x\equiv1 \mod{p}$ or $x\equiv p-1 \mod{p}$, where $p$ is a prime? The argument I have in mind is setting up a bijection, like in ...
-3
votes
2answers
26 views

Show that $a c\equiv b c\pmod m,\;a. b, c, m \in \mathbb Z$ and $m \geq 2 $ does not imply $a\equiv b \pmod m$ [closed]

Show that $a c\equiv b c\pmod m$ with $a. b, c, m \in \mathbb Z$ and $m \geq 2 $ does not imply $a\equiv b \pmod m.$
1
vote
1answer
29 views

Solve the following congruence for x (Modulo Question)

I need help in a question that I'm having a hard time understanding... It is asking to determine the congruence for $x$ and expressing the answer in the range 0-1000: $$ 200 . x = 13 \pmod{1001} $$ ...
0
votes
0answers
16 views

Is there any convention regarding the order of operation of the binary modulo operator?

Is there any predominant convention as to where the binary modulo operator (i.e., the variant of the modulo operator that is not applied to a whole equation) ranks in the order of operations, in ...
2
votes
3answers
43 views

Is modular arithmetic defined for all rational numbers (with denominators coprime to modulus)?

In the expression $\frac{1}{b}\pmod m$, where $(b,m)=1$, is $\frac{1}{b}$: a) a rational number (and so rational numbers are defined in modulo arithmetic using multiplicative inverses)? b) just ...
1
vote
0answers
26 views

Computation of large powers

How do I check if $2^{123456789}$ is divisible by 9? I tried using modular exponentiation but it is way too tedious. Is there an easier or faster way to solve it? Thanks!
1
vote
1answer
34 views

Primitive roots for a number

I want to show if a number a is a primitive root$\pmod{n}$ Is there a way to show this without raising a to all the powers between 1 and n-1?
1
vote
1answer
15 views

Internal and Direct Product question, need help with explanation

I am asked to express a group G={1,7,17,23,49,55,65,71} under multiplication modulo 96 as an external and internal direct product of cyclic groups. However I also have an example to help with it, but ...
2
votes
2answers
45 views

A question on divisibility

For what values of $x,y \in \{1,2,3,...9 \}$, does $$10x+y \space\mid 100x + y $$ ? What approach should I take for solving this problem ?
1
vote
0answers
23 views

Chinese Remainder Problem with three equations

Let's consider: $$*\begin{cases} 7x \equiv 2 \mod 5\\ 3x \equiv 2 \mod 4 \\ 5x \equiv 2 \mod 6 \end{cases}$$
1
vote
2answers
32 views

Principal Square Root mod

"Theorem: let p be a prime satisfying $p=3\bmod4$. Then for an integer y which is a square modulo p, $x=y^{(p+1)/4}\bmod p$ is a square root mod p of y. That is, $x^2=y\bmod p$. This is called the ...
0
votes
0answers
23 views

Strong pseudoprime base b

Show that the composite number 1281 is a strong pseudoprime base 41. "$n-1=2^rm$, then n is a strong pseudoprime base b if either $b^m=1modn$ or $b^{2^sm}=-1modn$" Ok so I have $n=1281$ and $b=41$ ...
0
votes
3answers
31 views

Modular equations: where did I make a mistake?

I want to solve the simultaneous congruences $$\begin{cases} 2x \equiv 4 \mod 8 \\ x \equiv 2 \mod 6 \end{cases} $$ My solution: $$2x \equiv 4 \mod 8 \iff x = 4l + 2 $$ $$x \equiv 2 \mod 6 \iff 4l + ...
0
votes
4answers
33 views

Modular arithmetic, very simple implications.

$$3t \equiv 1 \mod 4 \Rightarrow t \equiv 3 \mod 4 $$ I don't understand that, so I'm asking for explain me. Thank, in advance, greetings.
0
votes
3answers
32 views

Finding divisibility of a number using modular arithmetic

Let N = 12345678910111213141516171819. How can I use modular arithmetic to show that N is (or isn't) divisible by 11? In general, how can I apply modular arithmetic to determine the divisibility of an ...
0
votes
2answers
23 views

Question about modular arithmetic notation

In this document: http://cims.nyu.edu/~kiryl/teaching/aa/les092603.pdf The ordered pair notation is used but it is never explained what it means. ex: ...
0
votes
1answer
46 views

Proof, that $a \equiv 1 \pmod{p}$

Let $n \in \mathbb{N}^{+} \smallsetminus \{{1}\}$ and $p = min\{p \in \mathbb{P} : p \mid n\}$. Also, let $a \in \mathbb{Z}$ and $a^n \equiv 1 \pmod{n}$ I need to proof, that $a \equiv 1 \pmod{p}$. ...
0
votes
1answer
48 views

How to show a number is not a sum of squares

I've been tasked with the following: Let $m$ and $n$ be positive integers, prove that $4^{n}(8m+7)$ cannot be written as the sum of three squares. I've already gotten the idea that I should do ...
1
vote
1answer
33 views

Modular arithmetic and using in well-ordering principle

I need to prove the following, but I do not know how to go about it. If $$ (*)\:\:\: x^{3} - y^{3}= 3^{n} $$ Then $$ x \equiv 0 (mod 3) \:\: and \:\:\: y \equiv 0 (mod 3)$$ In addition, ...
-1
votes
2answers
57 views

Units in the ring $\mathbb{Z}(\omega)$

If $\omega \not= 1$ is a cube root of unity in $\mathbb{C}$, show that the units in the ring $\mathbb{Z}[\omega]$ are the elements of modulus 1. Hence, or otherwise, show that $U(\mathbb{Z}[\omega]$ ...
2
votes
1answer
36 views

computing $29^{25}$ (mod 11)

I'm trying to learn how to use Fermat's Little Theorem. $29=2\cdot11+7 \Rightarrow 11\nmid29$ by the theorem we have $29^{10}\equiv 1$(mod 11) $25=10\cdot 2 + 5$ $ ...
0
votes
1answer
15 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
-2
votes
1answer
27 views

What is the most efficient way to evalaute the function $f(N, R) = F(N)/(F(N-R)*F(R))$ where $F(N) = 1^1*2^2*…*N^N$? [closed]

In particular goal is to find $f(n,r)\mod(m)$ for given values of n, r, m and m is a prime number. $f(n,r) = F(n)/(F(n-r) * F(r))$ where F(n) = $1^1 * 2^2 * 3^{3} *... * N^N $ Here is the python ...
2
votes
0answers
40 views

Compute digits of a number.

The question is what the last $10$ decimal digits of $2^{3^{4^{5^{6^{7^{8^9}}}}}}$ are? I do not get the following solution and its motivation. I would appreciate if someone would shed light on it. ...
0
votes
0answers
12 views

Pari/ GP Mod function

I am fairly new to using Pari/GP. Trying to compute below formula: y1=Mod((g^a1)*(y^a2),p); When I try to output y1, instead of giving me the value of Mod ...
3
votes
1answer
58 views

Congruence for the sums of odd powers of integers [duplicate]

Does someone know how to prove ***EDIT by induction**** that for all integers $n\ge1$, $k\gt0$ $$\sum\limits_{i=1}^{n} {i^{2k+1}}\equiv 0\ \ \ \pmod{\frac{n(n+1)}{2}}$$ I thought this should be a ...
0
votes
2answers
29 views

Prove divisibility

We have the following proposition: $$P(n): 13^n+7^n-2\vdots 6$$. Prove $P(n)$ in two ways. I know that one of them is mathematical induction. I don't know many things about the other one, I know ...