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
3answers
48 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
68 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
83 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
54 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
159 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
53 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
215 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
61 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
60 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
66 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
50 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
126 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
82 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
76 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
65 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
1answer
39 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
67 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
42 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
66 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
92 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
80 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
75 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
99 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
45 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) = ...
1
vote
2answers
44 views

Proof relating to the order of $a \mod n$?

The proof required is to show that $\operatorname{ord}_n(a^j) \mid\operatorname{ord}_n(a)$, for any positive integer $j$. I have considered using a proof by contradiction, but am having trouble going ...
0
votes
1answer
213 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
92 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.
0
votes
2answers
32 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
39 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
58 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
43 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
38 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 ...
3
votes
2answers
116 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
17 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
31 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
265 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
51 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
76 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 ...
0
votes
0answers
67 views

Matrix Induction proofs using $\rm mod$.

Please could someone advise me on where to even start with this question. Thanks in advance Let $A$ be an $n\times n$ matrix, for some $n\geqslant 1$. Given any prime number $p\gt1$, write $A_p$ for ...
1
vote
4answers
76 views

How to find all elements in Z/80 that have multiplicative inverses.

I need to find all the elements in Z/80 that have multiplicative inverses. Z/80 is not a field, so I know not every element will have an inverse. Is there a shorter way than just writing out the ...
0
votes
0answers
55 views

How to calculate sum of digit of a power

Find the sum of the digits of: $$\left\lfloor\frac{k^{h+1}-1}{h-1}\right\rfloor$$ I need to calculate sum of digits in answer. Note as $k$ and $h$ can be a very big value, answer is getting ...
1
vote
3answers
69 views

Calculating $x^{103} \equiv 2 \pmod{143}$

I need to find x, given that: $0\leq x \leq 143$ and $x^{103}\equiv 2 \pmod{143}$. I tried to use Euler's theorem $p(143)=120$, but it didn't help.
0
votes
0answers
82 views

Sum of the jumbled digits of $abc_{10}$ is $3194$

In the book that I am reading, the author denotes $abc_{10}$ as $100a+10b+c$ where $a, b, c \lt 10$. So if $a = 3$, $b=2$ and $c=8$ then $abc_{10} = 328$. The author asks the following problem: In ...
6
votes
2answers
5k views

What are primitive roots modulo n?

I'm trying to understand what primitive roots are for a given $\bmod\ n$. Wolfram's definition is as follows: A primitive root of a prime $p$ is an integer $g$ such that $g\ (\bmod\ p)$ has ...
0
votes
1answer
46 views

Matrix double modulo multiplication to get identity

I have to multiply to matrices A and B which can consist of numbers 0,2,3,4,5,6 to get an identity matrix, however multiplication happens with moduli after every ...
0
votes
1answer
38 views

How to show $2^{k+2}$ divides $3^{2^k}-1$ but $2^{k+3}$ doesn't?

I've got a task: Find highest power of 2 that divides $3^{2^k}-1$ so i wrote few terms and guessed that it's $2^{k+2}$, now i should show it. I tried by induction, but what i got appeals to me as a ...
0
votes
1answer
29 views

How to prove $N=13\times12v+6\times19u$ is a solution for the system?

Well, I have a system of congruences it is : $$n\equiv13\pmod{19}$$ $$n\equiv6\pmod{12}$$ I'm trying to prove that for any pair of integers $(u,v)$ the number $N=13\times12v+6\times19u$ is a solution ...
1
vote
0answers
39 views

Floor function inequality: $\frac{n^2}{x}-\left\lfloor\frac{n^2}{x}\right\rfloor+\frac{2n+1}{x}-\left\lfloor\frac{2n+1}{x}\right\rfloor<1$

I would like to dissect the following inequality to figure out its properties. $$\frac{n^2}{x}-\left\lfloor\frac{n^2}{x}\right\rfloor+\frac{2n+1}{x}-\left\lfloor\frac{2n+1}{x}\right\rfloor>1$$ ...