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

Fundamental theorem of algebra in modular arithmetic

suppose you have a polynomial $P(x) = a_0+a_1x+...+a_kx^k$. How can you prove that at most $k$ numbers satisfy $P(x) \equiv 1 \mod n$ ? To me this looks like the fundamental theorem of algebra, ...
0
votes
1answer
16 views

When will function output have a specific decimal component

Given a function f(x), is there any way to predict when the function will give a specific decimal part without brute-force iteration over possible x-values? Ex. f(x)=100/a^2 with arbitrary a, when ...
1
vote
1answer
32 views

Find coordinate $y$ of an elliptic curve point

If I have an elliptic curve over a finite filed $F_p$ ($p$ is prime) defined as $$ y^2 \equiv x^3 + ax + b\pmod p,$$ such that $4a^2 + 27b^2 \neq 0$ and suppose I have only given the coordinate $x$, ...
1
vote
2answers
79 views

Solving $a^2+b^2\equiv 0$ mod $c$ for distinct integers $a,b,c$ constrained between two consecutive squares

Show that for any natural number $n$, between $n^2$ and $(n+1)^2$ one can find three distinct natural numbers $a,b,c$ such that $a^2+b^2$ is divisible by $c$. A friend and I found a general case that ...
1
vote
1answer
17 views

Bound on the degree of a determinant of a polynomial matrix

I want to implement a modular algorithm for computing the determinant of a square Matrix with multivariate polynomials in $\mathbb{Z}$ as components (symbolically). My idea is first to reduce the ...
3
votes
0answers
38 views

Strange things on WolframAlpha: derivation, modulo and doubling result

I asked WA what is the derivative of $\frac1{\cos((x \bmod \pi/2)-\pi/4))}$ equal to for $x=0$. A very strange result came out. The exact result is $-\sqrt2 \mathsf{Mod}^{(1,0)}(0,\frac\pi2)$, ...
0
votes
1answer
7 views

contextual system of congruences

A large wholesale company for books uses three different types of shelf in their ware- houses. Their capacity is gauged in terms of a certain specimen book of average size, known under the nickname ...
3
votes
2answers
18 views

How do I eliminate mod from an expression?

If I have an expression such as $$ x = ((a \bmod b) - s) \bmod t, \quad 0 < a < b $$ And I want to step to $$ x = (a - s) \bmod t $$ Is acceptable to jump straight from the first expression to ...
1
vote
3answers
73 views

A question about modular arithmetic

$2^{35}\equiv x\bmod 561$ I have seen this in my book but there is no solution in it, how can we find x?
0
votes
3answers
21 views

Find all solutions for modulo equation

Given $(133x \equiv 107) \pmod{91} , x \in N $ My first attempt was to do: $133x - 91z \equiv 16 \pmod{91}$ $133x - (91z + 16) \equiv 0 \pmod{91}$ $133x - 16 \equiv 0 \pmod{91}$ From there on I do ...
2
votes
1answer
14 views

Polynomial factorisation on integers modulo n

Is there a known (efficient) algorithm to compute the list of factors of a polynomial modulo $n$ (for any integer $n$)? For example in $\mathbb Z_8$, $X^2+2X$ has a list of 4 factors (multiplicity 1 ...
0
votes
1answer
26 views

Proof that the repeating block of digits in 1/x is at max x-1?

The question is self-explanatory, I suppose. Example, the maximum number of digits in the repeating block of 1/17 is 16. Thanks in advance.
0
votes
1answer
45 views

To prove that ${2+i \choose i}\equiv k \mod n$ is not possible that $k=0,1,\ldots,n-1 \forall i\ge 0$ and $i \in \mathbb{Z}$ and $n$ is odd.

To prove that ${2+i \choose i}\equiv k \mod n$ is not possible that $k=0,1,\ldots,n-1 \forall i\ge 0$ and $i \in \mathbb{Z}$ and $n$ is odd. This is a problem from ISI 2014 written test in a little ...
2
votes
3answers
98 views

How do you prove that $ n^5$ is congruent to $ n$ mod 10? [duplicate]

How do you prove that $n^5 \equiv n\pmod {10}$ Hint given was- Fermat little theorem. Kindly help me out. This is applicable to all positive integers $n$
2
votes
1answer
43 views

The existence of primitive algebraic units modulo 3

Consider the problem of computing $$\sqrt{2} \mod 3 $$ Whereas we seek a number $n$ such that $n^2 \equiv 2 \mod 3$ and furthermore it is known that both $n$ and $2n$ will satisfy this property, ...
1
vote
5answers
97 views

If $a, b$ are relatively prime proof.

Prove that if $a$ and $b$ are relatively prime integers and $ab$ is a perfect square so are $a$ and $b$. Show by counterexample that the relatively prime condition is necessary. I dont know how ...
-3
votes
2answers
35 views

Proofs for modular arithmetic

$\rm(a)$ Prove that for any pair $a,b$ of positive integers there are integers $x,y\in\Bbb Z$ such that $ax+by=\gcd(a,b).\ $ (Hint: Use the well-ordering principle on the set of integer linear ...
2
votes
0answers
29 views

Given any integers $a,b,c$ and any prime $p$ not a divisor of $ab$, prove that $ax^2+by^2\equiv c\pmod{p}$ is always solvable.

The fact that there are $\dfrac{p+1}{2}$ quadratic residues seem to me to help solving the question, but I don't know how to go on from that point. Could you give me any hint?
1
vote
1answer
33 views

Divisibility of sum of exponents

Consider the sequence $$r, \ ra, \ ra^2, \ ra^3, ... \ , ra^n \mod M $$ such that: $$ ra^{n+1} \equiv r \mod M$$ and $a \ne 1$ and $a,r$ are both coprime to $M$ Is it always true then that: ...
0
votes
2answers
40 views

Let $p$ be a prime number such that $p \equiv 3( mod$ $4$). Show that $x^2$ $\equiv$ -1 $(mod$ $p)$ has no solutions. [duplicate]

Let $p$ be a prime number such that $p \equiv 3( mod$ $4$). Show that $x^2$ $\equiv$ -1 $(mod$ $p)$ has no solutions. I noticed that this is equivalent to proving $ x^2\equiv 2(2k+1) $ $(mod $ $p)$. ...
1
vote
1answer
38 views

Modulus Implication

If $a, \ b, \ c, \ d$ are integers and $a \equiv b \pmod c$ then $d^a \equiv d^b \pmod c$. True or false? I changed this statement to If $a,b,c,d$ are integers and $c\mid (a-b)$ then $c\mid (d^a - ...
2
votes
2answers
102 views

Prove that $a^n+b^n \equiv (a+b)^n \mod n$, if $n$ is prime and $a,b$ are integers.

What is the best method to prove that if $n$ is prime and $a,b$ are integers $a^n+b^n \equiv (a+b)^n \mod n$, ?
0
votes
1answer
43 views

Helping solve mod problems

I am having trouble solving the below problems. My teacher taught us to write out the solutions by hand.. but I really think there is an easier way to do the higher numbers. Thanks!
0
votes
1answer
34 views

Solution for generalized Euler's Theorem $a^m\equiv a^{m-\phi(m)} \pmod{m}$?

The above identity holds for any integer $a$. Since my solution(?) does seem neither elegant nor rigorous enough, I want to get some advice to improve it. My solution: If $(a,m)=1$, this identity is ...
0
votes
1answer
55 views

How do I find the inverse of $e \bmod (p-1)(q-1)$?

I'm trying to find this inverse modulo to set up a solution for an RSA cipher. I haven't the slightest how to go about this. When I looked up the formula for such a question, it states: $$ d \equiv ...
0
votes
0answers
25 views

Divisibility Method

Is there exist any known method to find divisibility rule of each and every rational number in any numeral system by analysing its reciprocal. And additionally it will give the remainder on division ...
1
vote
2answers
56 views

Compute $F_{1000} \bmod F_{11}$, where $F_n$ denote the Fibonacci numbers

Compute $F_{1000} \bmod F_{11}$, where $F_n$ denote the Fibonacci numbers. Progress: $F_{11}=89$ . I believe you should find the period of $F_n \bmod 89$ and use that to solve it. But I'm not not ...
0
votes
1answer
39 views

Quadratic residue modulo $p$ iff quadratic residue module $p^k$

Let $p$ be an odd prime, $a\in \mathbb{Z}$ with $(a,p)=1$. I am trying to show that if $a$ is a square modulo $p$ then it is a square modulo $p^k$. I managed to prove this using an exponential ...
-1
votes
1answer
32 views

Large Modular Arithematic Exponentiation [duplicate]

How do I calculate $2^{65536} \pmod{2^{31} -1}$ $3^{256} \pmod{2^8 +1}$ Please help?
-1
votes
1answer
35 views

$p>3$ prime, show that there exists $0<x,y<\sqrt{p}$ so that $p$ divides $cx-y$

Let $p>3$ be a prime number that does not divide $c$. Show that if $p>3$ there exists $x$ and $y$ with $0<x,y<\sqrt{p}$, such that p divides $cx-y$. I believe I've shown the above but for ...
0
votes
4answers
56 views

$a \equiv b \pmod n$ and $c\equiv d \pmod n$ implies $ac \equiv bd \pmod n$

Given that $a \equiv b \pmod n$ and $c\equiv d \pmod n$, I need to prove that $ac \equiv bd \pmod n$ So far, I've only managed to deduce that $a+b \equiv c+d \pmod n$. I don't know if this is usable, ...
0
votes
1answer
66 views

Find the largest integer $n$ such that $10^n$ divides $10^6!$

Let $N=10^6!$ Find the largest integer $n$ such that $10^n$ divides $N$. Furthermore, compute the first digit and the last non-zero digit of $N$. I have some ideas that you should be able to use ...
1
vote
1answer
66 views

Compute $F_{1000} \bmod 1001$, where $F_n$ denote the Fibonacci numbers

Compute $F_{1000} \bmod 1001$, where $F_n$ denote the Fibonacci numbers. I have tried using the fact that $F_{n^k} \bmod F_n = 0, k=1,2,3,...$ but that doesn't get me anywhere. Thanks!
1
vote
2answers
73 views

Solving $x^2 + 96=0$ in $\mathbb{Z}_{100}$

I'm trying to find all solutions to $x^2 + 96=0$ in $\mathbb{Z}_{100}$. $x^2 + 96 \equiv 0 \bmod 100$ implies that $x^2 + 96 \equiv 0 \bmod 2$ and $x^2 + 96 \equiv 0 \bmod 5$. $$x^2 + 96 \equiv 0 ...
1
vote
3answers
79 views

Does $p \equiv q \pmod a \implies p \bmod a = q \bmod a$?

I'm trying to understand the notation $p \equiv q \pmod a$. Does does it implies that $p \bmod a = q \bmod a$? for example: $$ \begin{align} 5 \bmod 7 &= 5 \\ 12 ...
3
votes
1answer
29 views

Group of numbers in residue number system of first $n$ primes

Denote $$\Pi_n = \Pi_{i=1}^n p_i$$ ie. the product of the first $n$ primes. Assume we have a number $m$. Denote $$L(m) = k \iff \Pi_{k-1} < m \le \Pi_{k}.$$ Assume also $L(1)=1.$ Now, if $L(m) = ...
0
votes
1answer
78 views

What is the remainder when $24^{1202}$ is divided by $1446$?

I tried remainder theorem but that does not simplify it. I tried factorizing $1446$ as $2\cdot3\cdot241$ and got remainders when numerator is divided by $2,3$ and $241$ individually but then I did ...
-1
votes
1answer
28 views

Congruents and modulo question- counterexample

I have tired an couple and none seem to be working
2
votes
1answer
68 views

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$.

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$. This is a problem from a selection to IMO 2014. I like thinking about this problem, it is ...
0
votes
2answers
24 views

Why does $y^{pq} ≡ y $[mod $pq$] imply $y^{pq} ≡ y [$mod $p$] and $y^{pq} ≡ y [$mod $q$]? $p, q$ prime.

Why does $y^{pq} ≡ y $[mod $pq$] imply $y^{pq} ≡ y [$mod $p$] and $y^{pq} ≡ y [$mod $q$]? where $p, q$ prime. I can't see it from re-writing it as $y^{pq} = y + kpq$ for some integer $k$, as you ...
1
vote
2answers
34 views

Solve by using modulo. Or something else

An infinite sequence of positive integers $a_1, a_2,\ldots$ has the properties that for $k\geq2$, the $k^\text{th}$ element is equal to $k$ plus the product of the first $k-1$ elements of the ...
1
vote
2answers
42 views

Property of modulo division

I wanted to check if it is true, that $$a^{3b} \pmod n = (a^{b} \pmod n)^{3}\ ?$$ For example when $a = 2, b = 4, n = 5$ I have that $2^{12} \mod 5 = 1$ and $(2^4 \mod 5)^3 = 1$ Is that always true, ...
0
votes
2answers
38 views

Property of Modular arithmetic

If I know that $$g^a \neq 1 \mod b$$ is that always true that if I will take a positive integer $c$ and count $(g^a)^c$, then $$(g^a)^c \neq 1 \mod b$$?
2
votes
2answers
31 views

Why is $a^{n/2} \equiv -1 \mod p$ but not necessarily -1 modulo a composite?

I'm going over a review sheet in preparation for my number theory final. We are asked to prove the following: |a| = 2r, show that $a^r \equiv -1\mod p$ a prime. Does this hold modulo n, where n is a ...
2
votes
2answers
41 views

Cannot find length of repeating block in decimal expansion for $\frac{17}{78}$

I am trying to find the length of of the repeating block of digits in the decimal expansion of $\frac{17}{78}$. On similar problems, that has not been an issue. Take for instance $\frac{17}{380}$. My ...
1
vote
1answer
15 views

Using information from a congruence to factor a number

I am being asked to factor $15347$ given that $7331^2 \equiv 1460^2 \pmod{15347}$. I've tried playing around with each of the numbers -- prime factorization, gcd, lcm, etc., but I can't find a ...
1
vote
1answer
26 views

finding $m$ from $c = m^e \pmod{n}$

I'm working through an RSA encryption example, and I'm being asked to solve $c = m^e \pmod{n}$ for $m$ given c, e, and n (along with its factorization.). Since I already have that information ...
2
votes
4answers
253 views

Find number x such that $x\equiv 4^{1002}\pmod{55}$

Find a natural number x, for $0 \le x \le 54$ such that is a solution for the following equation: $$x\equiv 4^{1002}\pmod{55}$$ This question was asked in an exam, so I expect that the answer is ...
0
votes
1answer
33 views

Simple modulo congruence operation

Find a number $n$, with $0 \leq n < 15$, so that $6 \times 7$ is congruent to $n$ modulo $15$ Please explain your work.
2
votes
2answers
40 views

Showing equality of primitive roots with quadratic non-residues.

Suppose that $p$ and $q = 2p + 1$ are both odd primes. Show that the $p − 1$ primitive roots of $q$ are precisely the quadratic non-residues of $q$, other than the quadratic non-residue $2p$ of ...