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
vote
3answers
39 views

What are the members of the set $A=7^{n}+5^{n}(mod35)$

I have this set $A=${$\ x \ \in \mathbb{N}|\ \exists \ n \ \in \mathbb{N}:$ $x \equiv 7^{n}+5^{n}$ (mod $35$) $ $, $ 35\gt x\ge 0$} I want to know how many members has this set? thanks in advance
0
votes
2answers
40 views

How to prove that $2^{2^{m}}-1 \equiv 0$ (mod $2^{2^{n}}+1$)

I'd like to solve this problem but I can't $\exists \ m,n \ \in \mathbb{Z}$ & $ m\gt n\ge 0$ $2^{2^{m}}-1 \equiv 0$ (mod $2^{2^{n}}+1$) Any ideas? Thanks in advance.
4
votes
3answers
200 views

Square roots modulo powers of 2

Experimentally, it seems like every $a\equiv1\left(\bmod\,8\right)$ has 4 square roots mod $2^n$ for all $n \ge 3$ (ie solutions to $x^2\equiv a\left(\bmod\,2^n\right)$) Is this true? If so, how can ...
3
votes
2answers
162 views

Number theory problem.Primes modules.

If $$a^p\equiv b^p \pmod p$$ where $p$ is prime prove that $$a^p\equiv b^p \pmod{p^2}$$ that problem was at my exam today on number theory and i just didnt have a clear mind to solve it.Although i ...
2
votes
2answers
54 views

Correct reasoning when proving the multiplication property in modular arithmetic?

I am trying to understand why this rule works: \begin{align*} a \equiv b \pmod c \quad k \equiv j \pmod c \qquad &\implies \qquad ka\equiv jb \pmod c \end{align*} I saw that the proof is ...
1
vote
1answer
20 views

Definition for a distance function over a residue class ring

I'm searching for a reasonable definition of a distance function $$d:\mathbb{Z}/n\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}\to\mathbb{N}_0$$ which satisfies $d(\overline{n-1},0)=1$ ...
3
votes
3answers
219 views

How to find the missing number?

A teacher intended to give a typist a list of nine integers that form a group under multiplication modulo 91. But one of the nine integers was inadvertently left out, so that the list appeared as ...
7
votes
1answer
97 views

$ 7\mid x \text{ and } 7\mid y \Longleftrightarrow 7\mid x^2+y^2 $

Show that $$ 7\mid x \text{ and } 7\mid y \Longleftrightarrow 7\mid x^2+y^2 $$ Indeed, First let's show $7\mid x \text{ and } 7\mid y \Longrightarrow 7\mid x^2+y^2 $ we've $7\mid x ...
1
vote
1answer
55 views

How Many of a Given Weekday Fall in a Month

A month can have either $31, 30$, or $28$ days excluding leap years. Suppose we want to know "how many Fridays are in a given month". By considering the maximal case where the first Friday falls on ...
1
vote
2answers
71 views

What is the remainder after dividing $(177 + 10^{15})^{166}$ by $1003 = 17 \cdot 59$

What is the remainder after dividing $(177 + 10^{15})^{166}$ by $1003 = 17 \cdot 59$? I have made several observations about the problem but I cant see how they lead me to an answer. Observation one: ...
0
votes
1answer
45 views

Polynomial Diophantine Equations

So in general how does one decide if: $$ a_0 + a_1x + a_2x^2 ... a_{n_1}x^{n_1} = b_1y + b_2y^2 ... + b_{n_2}y^{n_k}$$ Has solutions for integers $x,y$ given real numbers $a_0, a_1. .. a_{n_1}, b_1 , ...
4
votes
2answers
91 views

For every integer, some multiple of it is of the form $99 \ldots 900 \ldots 00$

The goal is to prove that for every positive integer $ z$ there exists a positive integer $a$ such that $az = 99 \ldots 9900 \ldots 00$. Let $a = \frac {99 \ldots 9900 \ldots 00}{z}$ That ...
0
votes
1answer
59 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
17 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
58 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
86 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 ...
0
votes
1answer
48 views

if $b^k$ is a primitive root, then $b$ is a primitive root

Any hints or strategies would be greatly appreciated: If $m$ is an integer and $b^k$ is a primitive root mod $m$, then $b$ is a primitive root mod $m$. I am reviewing material from my elementary ...
1
vote
1answer
101 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
50 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
12 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
28 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
84 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
31 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
50 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
58 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
52 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
127 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
50 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
141 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 ...
2
votes
0answers
55 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
49 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
60 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
47 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
125 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
61 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
57 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
63 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
32 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
61 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
62 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
38 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
41 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
64 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
81 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 ...
2
votes
1answer
75 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
74 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
88 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
42 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
170 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 ...
2
votes
1answer
89 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.