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

-1
votes
1answer
26 views

If $\gcd(k, p-1) = 1$ show that $x^k \equiv l \pmod{p}$ has at most one solution.

Assume that $k$ is a natural number and $p$ is a prime where $\gcd(k, p-1) = 1$ Let $l$ be an integer show that $x^k \equiv l \pmod{p}$ has at most one solution. I'm pretty sure I have to somehow use ...
0
votes
0answers
22 views

Mod devision - there are two different solutions

This is my working The question asks us to find the solution in the form of x = k (mod 65). But I also found a solution in the form of mod (13), but they are totally different. Which one is correct? ...
3
votes
2answers
67 views

Show that the cube of any integer is congruent to $0$ or $\pm 1 \pmod 7 $

For any integer, $n$, show that $n^3 \equiv 0$ or $\pm 1(\mod 7)$. Use theory of congruences So I thought about a couple of ways to go with this. I thought about showing $7|n^3$ or $7|n^3\pm1$ to be ...
0
votes
4answers
65 views

A positive integer (in decimal notation) is divisible by 11 $ \iff $ …

(I am aware there are similar questions on the forum) What is the Question? A positive integer (in decimal notation) is divisible by $11$ if and only if the difference of the sum of the digits in ...
0
votes
2answers
49 views

Let G be a group with identity $e$. If $a,b$ are integers, and $x$ is an element in G such that $x^a=e$ and $x^b=e$, then show that $x^{gcd(a,b)}=e$

I'm not really sure how to start this proof. Should I start with 3 different cases, $a=b, a<b, a>b$? If $a=b$, then of course $gcd(a,b)=a=b$ and so $x^{gcd(a,b)}=x^a=x^b=e.$ If $a<b$, ...
0
votes
0answers
48 views

Suppose that n=ab, where a ≥ b > 2 and gcd (a,b)=1. By working mod a and mod b, prove that there are at least 4 different solutions to x^2.=1 mod n.

I've started by stating that if $x^2=1\mod n$, since $n=ab$ and $gcd(a,b)=1$, then $x^2=1\mod a$ and $x^2=1\mod b$. Now, I know that for $a,b \gt 2$, there will always be at least two solutions for ...
0
votes
1answer
11 views

Find all Dirichlet characters modulo $p$

In my elementary number theory class we define the following: Let $p$ be a prime, and let $\mathbb{Z}_p^*$ relatively prime residues modulo $p$. A Dirichlet character modulo $p$ is defined as a ...
1
vote
3answers
32 views

Find the remainder of $\sum_{i=0}^{99} 2^{i^2}$ when dividing by 7 and determine if the quotient is even or odd

I've recently had this problem in an exam and couldn't solve it. Find the remainder of the following sum when dividing by 7 and determine if the quotient is even or odd: $$\sum_{i=0}^{99} 2^{i^2}$$ ...
1
vote
2answers
18 views

A question on “law of congruence of modulus”

I have a quick question about the law of congruence of modulus, which states "Let $a•b≡a•c \,(\mod m)$, where $a$ is not equivalent to $0$,$ \mod m$. We can cancel $a$ only when $a$ and $m$ are ...
2
votes
3answers
52 views

Remainder of $2^{100} (\mod\ 89)$

I am having trouble coming to the answer on this question: Find the remainder when $2^{100}$ is divided by $89$. (Hint: Simplify $2^{10} \pmod{89}$ first.) So I went with the hint and found $2^{10} ...
0
votes
1answer
33 views

Solving a linear system in $\mathbb{Z}_{12}$?

Let $\alpha \in \mathbb{Z}_{12}$. I need to solve the following system in $\mathbb{Z}_{12, +, \cdot}$ for every $\alpha$ : \begin{cases} 6x + 5y = 0 \\ 8x + y = \alpha \end{cases} I'm confused because ...
0
votes
2answers
14 views

Arithmetic with congruence classes

I need to compute the following expression in $\mathbb{Z}_{5, +, \cdot}$ : $$ [2]_5^4 - [4]_5^4 \cdot [3]_5^4 \cdot [2]_5^4 $$ I'm not sure what is the best way to do this. Should I determine all the ...
2
votes
1answer
33 views

Proving an identity involving floor function

Prove that : $$\left \lfloor \dfrac{2 a^2}{b} \right \rfloor - 2 \left \lfloor \dfrac{a^2}{b} \right \rfloor = \left \lfloor \dfrac{2 (a^2 \bmod b)}{b} \right \rfloor $$ Where $a$ ...
0
votes
3answers
47 views

If the sum of two $p$th powers is divisible by $p$, then it is divisible by $p^2$

If $p > 2$ is a prime and $p | (x^p + y^p)$, then show that $p^2 | (x^p + y^p)$ I have been stuck on this problem for a while now. (Though my textbook is prone to mistakes so the original ...
1
vote
2answers
21 views

Show $x^k \equiv a\space(mod\space p)$ has at most one solution when $k$ and $p-1$ are coprime

Let $p$ be a prime, and $k\in \mathbb{N}$ such that $hcf(k, p-1) = 1$. If $a$ is an integer then show that $x^k \equiv a \space\text{mod}\space p$ has at most one solution. So far i've tried assuming ...
0
votes
0answers
19 views

Field of the form $\{a+bi|a,b\in \mathbb{F}_p\}$

Artin, Algebra, Chapter 3, Ex 1.11 Consider whether the set of symbols $\{a+bi|a,b\in\mathbb{F}_p\}$ forms a field, if the laws of composition are made to mimic addition and multiplication of complex ...
1
vote
0answers
69 views

Finding an Elliptic Curve with 103 points

I am trying to solve the following problem: Find an elliptic curve over F101 with 103 points. I know all of the equations when needing to find alpha, and beta and all that when I am given two points ...
2
votes
1answer
50 views

Use of modular arthemitic to prove identity

While studying primes that are either $2^n+1$ or $2^{n}-1$, I noticed this relationship. $2^{(n-1)/{2}}-(-1)^{(n^{2}-1)/{24}}\equiv 0\mod n$ iff $n$ is prime for $n\ge5$. My question is, how can I ...
0
votes
0answers
8 views

Quadratic modular constrained problem.

Given $r\in(0,1)$ and small $\epsilon>0$ is there minimum $n_{r,\epsilon}$ such that at every $n>n_{r,\epsilon}$ there are distint integers $p,q,x,y$ where $$p,q\approx n^{2r},x\approx ...
0
votes
1answer
19 views

Given that $2^ny+1 \mid x^{2^n}-1$, $\forall n \in \mathbb{N}$. Prove that $x=1$

Given that $2^ny+1 \mid x^{2^n}-1$, $\forall n \in \mathbb{N}$. Prove that $x=1$ I can't find a way to start... Any hint will be helpful.
0
votes
1answer
14 views

Modular arithmetic with negative numbers

Is this correct -347 mod 6 = -5 Or is this correct -347 mod 6 = +1
0
votes
3answers
37 views

Modulo with negative numbers

When I input this in wolfram I get false -347 mod 6 = 5 When I input this I get true -347 mod 6 = 1 And yet I know $-5 \equiv 1$ And additionally $-6*57 - 5 = -347$ but ...
0
votes
2answers
30 views

Modulo of a negative number

Why is $347 \bmod 6 = 5$ but $-347 \bmod 6 = 1$ What is the difference?
0
votes
0answers
7 views

Graph and Stitch Piecewise Function

I am trying to develop a model to describe the rate of something increasing. It increases 88983 for 1.26s, then stops for 2.3s. It repeats this cycle indefinitely. The best I could come up with is: ...
3
votes
1answer
47 views

Conjecture about odd primes

For each odd prime $p$ there exist $n\in\mathbb{N}$ such that $p\equiv n^2 \text{ (mod }\varphi(n^2))$, where $\varphi$ is Euler's totient function. I'm developing my Forth based computational ...
2
votes
0answers
20 views

Mathematical development with Polynom modulo n

I have to implement a method seen in an article, and I'm stuck with some mathematical development. The article is on iEEE Xplore, so I'll try to be as specific as I can. It's about pairing-based ...
2
votes
2answers
31 views

Power sums over additive subgroups of finite fields

I recently read a thread on this site that solved the following problem: let $K:=\mathbb{F}_q$ be a finite field of $q$ elements and $i$ an integer. Then $\sum\limits_{\alpha \in K} \alpha^i = 0$ ...
0
votes
0answers
14 views

Products of bounded numbers whose residues agree.

Given small $\epsilon>0$, $0<q<r<r+s=1$ and large enough $n\in\Bbb N$ is it always possible to find coprime $a,b$ and coprime $c,d$ such that $$a\approx n^{q+\epsilon},b\approx ...
0
votes
1answer
21 views

Proof involving two's complement arithmetic of binary numbers

I have a "clock" - a 32-bit unsigned number - that wraps around from $4,294,967,295$ ($2^{32}-1$) back to $0$. At point 'A' in time, I stamp the clock into a variable - call it $x$. Later, at point ...
0
votes
0answers
15 views

Congruences, modular

I need to solve this problem with the Chinese Remainder Theorem: $$ x = b_1N_1x_1+b_2N_2x_2 + ...+b_kN_kx_k $$ N = 17*13*12 = 2652 $$\begin{cases} x≡7 \pmod{17} \\ x≡9 \pmod{13} \\ x≡3 \pmod{12} ...
1
vote
3answers
28 views

$2^a \pmod{13} \equiv 5$ solve to find a formally

I can seem to find any formal proof that would help me derived a knowing $2^a \pmod{13} = 5$ ? The following is given $2^a \pmod{13} = 5$
-1
votes
2answers
31 views

large modular arithmetic without powers

How would you find the answer to this $$111453 \cdot 1812337 \bmod(10)$$ I know how to do it if given powers but don't know how to solve something like this above.
0
votes
1answer
16 views

Worded linear congruence problem-Days/Years

The Melbourne cup is run every year on the first Tuesday in November. The US presidential elections are held every four years on the day after the first Monday in November. George W. Bush was elected ...
1
vote
1answer
19 views

Modular zero of a function

Is there a quick and dirty way to find the modular zero of a function, such that f(x) = 0 (mod p), p being a prime. E.g. f(x) = x^2 - 5x + 1 and p = 7. It's quite easy to find that for x = 6 the ...
1
vote
1answer
37 views

How to split congruences so moduli are prime powers?

If I have the linear congruence x=5 mod 84, is this equal to x=2 mod 3, since 3|84? This seems too easy.
2
votes
1answer
20 views

What exactly are strands in a quandle coloring?

From this slide on page 25, the system of equations: $$a = b \triangleleft (a \triangleleft b)$$ $$b = (a \triangleleft b) \triangleleft (b \triangleleft (a \triangleleft b))$$ Reduces down to: ...
2
votes
1answer
47 views

Prove that $11^{2n}+5^{2n+1}-6$ is divisible with $24$ for $n∈ℤ^+$

Prove that $11^{2n}+5^{2n+1}-6$ is divisible with $24$ for $n∈ℤ^+$ I've been trying to solve it by using modulo; $11^{2n}+5^{2n+1}-6≡ (11^2 mod24)^n + 5*(5^2mod24)^n-6 = 1^n + (5*1^n)-6 = 0$ Is this ...
0
votes
2answers
42 views

Finding modular inverse of every number mod 26?

I am looking at cryptography, and need to find the inverse of every possible number mod 26. Is there a fast way of this, or am i headed to the algorithm every time?
1
vote
0answers
29 views

How do i prove that $ Z_n $ is a subring of $ Z_m $ using the subring test?

Let $n, m \in Z^+ \setminus {1} $. Assume $ n|m $. How do i prove that $ Z_n $ is a subring of $ Z_m $ using the subring test? Do i just have to follow the 3 conditions for the subring test? or there ...
-1
votes
0answers
24 views

Solutions to a congruence in a product of cyclic groups

I'm trying to answer the following question. How many solution are there for the equation $x\equiv 0 \pmod p$ in $\mathbb{Z}_{p}\times \mathbb{Z}_{p^{3}}\times \mathbb{Z}_{p^{5}}$
0
votes
0answers
19 views

Discrete Math - RSA Encryption problem

I am doing practice problems for my upcoming final exam, and am having trouble with this RSA encryption problem. If any one could check to see if i did these correctly, it would be greatly ...
2
votes
1answer
68 views

How do I find the smallest positive integer $a$ for which $a^n \equiv x \pmod{2^w}$?

$x$ is fixed odd positive integer value. $n$ and $w$ are fixed positive integer values. $a$ is positive integer value. I am interested for $n=41$ and $w=160$, but would appreciate a general ...
2
votes
0answers
27 views

A problem in modular arithmetic.

Given large $n\in\Bbb N$ is there many $a,b\in(n,2n)$ with $\gcd(a,b)=1$ and $q,r\in(n^4,2n^4)$ with $\gcd(a,bq)=\gcd(ar,b)=1$ and $c,d\in(n^3,2n^3)$ with $-n<-x=q\bmod c,-y=r\bmod d<0$ with ...
0
votes
1answer
43 views

$3x + 1 = 2^i$ only has integer solutions when $i$ is even

I came across this question while looking at powers of 2 and investigating number theory. I found it quite interesting, unfortunately I would say that my skills in number theory are far too primitive ...
0
votes
2answers
43 views

Why is this valid for modulus?

My teacher asked if this statements was valid: $$ 37 + 50 \equiv 27 \pmod {60} $$ Which is basically $$ 87 \equiv 27 \pmod {60}$$ and he said this is true. But how? I know that $87 \bmod {60}$ is ...
0
votes
0answers
18 views

How to compute large number fraction modulo, when divisor has no modulo inverse?

I'm trying to compute such number: $a \equiv 0 \pmod m$ and $a\equiv0 \pmod 3$. $a$ can be large but divisible by $3$ and $m$ is not guaranteed to be coprime with $3$. The solution which I came up ...
1
vote
3answers
26 views

Modular Algebra in Finding Roots

I'm playing around with this problem. $$x^{2} - 2x + 10 \equiv 7 \ \text{mod} \ 6$$ Find the equivalence class(es) in $\mathbb{Z_{6}}$ solving this. The following doesn't work out: ...
1
vote
0answers
12 views

Bound on smallest $n$ for consistency of a system of equations?

Given small $\epsilon>0$ how small should $n\in\Bbb N$ be such that if $a,b,c,d,q,r,u,v,x,y,m,m'\in\Bbb N$ with $gcd(a,b)=gcd(a,x)=gcd(b,y)=1$ the following relations can hold with constraints ...
6
votes
3answers
134 views

The sequence of integers $1, 11, 111, 1111, \ldots$ have two elements whose difference is divisible by $2017$

Prove that the sequence $\{1, 11, 111, 1111, .\ldots\}$ will contain two numbers whose difference is a multiple of $2017$. I have been computing some of the immediate multiples of $2017$ to see how ...
3
votes
4answers
65 views

Fermat's little theorem question: why isn't $a^p \equiv 1$?

Fermat's little theorem says that $a^p \equiv a \pmod p$. I have kind of a stupid question. Since $p \equiv 0\pmod p $, why isn't $a^p \equiv a^0 \equiv 1 \pmod p$ ?