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

Modulus differentiation

For a Java project, I need to find a way to compute the derivate of a modulus function like $$f(x) = g(x) \pmod{h(x)}$$ for any value of $x$. I know that the modulus function is discontinuous. If ...
1
vote
1answer
54 views

Show the congruence $x^{p-1}\equiv 1\pmod{p}$ has $p-1$ solutions

Question: Let $p$ be prime. show the congruence $x^{p-1}\equiv 1\pmod{p}$ has $p-1$ solutions Attempt: I know by Lagrange's theorem that this congruence will have at most $p-1$ solutions since $p-1$ ...
0
votes
0answers
9 views

Modular arithmetic of rotation a triange

A triangle is an n-gon with 3 rotational symmetries and 3 reflection symmetries. Each rotation is 120 degrees. Suppose the triangle begins with initial angle 240 degrees and rotates through 240 ...
0
votes
1answer
56 views

How to solve congruence modulo equations?

While studying Affine Cipher in cryptography it tells that we need to solve a system of modulo congruence equations. The equations are: $8\alpha+\beta\equiv 15 \pmod{26}$ $5\alpha+\beta\equiv 16 ...
0
votes
1answer
32 views

Show that if $a, b$ and $m$ are integers such that $m \geq 2$ and $a \equiv b \pmod{m}$, then $\gcd(a, m) = \gcd(b, m)$

Problem 1 (#3.5.32). Show that if $a, b$, and $m$ are integers such that $m \geq 2$ and $a \equiv b \pmod {m}$, then $\gcd(a, m) = gcd(b, m)$. Proof. Let $d = \gcd(a, m)$ Then $d \mid a$ and $d ...
2
votes
1answer
39 views

Hensel's lemma modular arithmatic example problem

In an example for Hensel's Lemma we have met the criteria to use Hensel's lemma and have begun to apply it in a Hensel's iteration. We have $f(x)=x^2+1$ and our initial $x_0=2$ is a solution ...
1
vote
1answer
37 views

Number of possible solutions in modular equation

I have given the result value $z$. I know that $$z \equiv x\cdot(x-1)\pmod p$$ where $p$ is prime and the value $p$ is fixed and given. I have also given the information, that $x \in \{m, M\}$, where ...
0
votes
1answer
31 views

Digital Signatures using RSA

RSA can be used for digital signatures this way: B creates $m$ (product of two primes), $r$ (a number for what gcd($r$, $\Phi(m)$ equals 1) and tells $m$ and $r$ A. B chooses $s$ which is the ...
1
vote
1answer
48 views

modulo RSA decrypt question

Given the following RSA generated public key: $P(3, 55)$. Which integer value should be chosen for $d$ to decrypt messages encrypted with $P$? Check your answer with $M = 8$ and $C = 17$. ...
3
votes
4answers
47 views

Find the following integer $ x $, s.t. $x \equiv 7^{57} \pmod {133}$

Find the following integers $x$: $x \equiv 7^{57} \mod 133$ I need to use fermat's little theorem for this problem which I know. It is for a prime number p. Then $a^{p-1} \equiv 1 \pmod p$ but I do ...
2
votes
2answers
32 views

Finding big exponential value

How to find the following most efficiently $$ A^{x} \bmod M $$ where $A,x\le10^{10}$ and $M$ is a quite big prime number.
0
votes
0answers
27 views

Reverse proof of Fermats Little Theorem [duplicate]

Let $n \in \mathbb{N}$. For all $x \in \{1,2,...n-1\}$ it is: $x^{n-1} \equiv 1 \text{ mod } n$. Show that $n$ is prime. This seems to be proving Fermat's little theorem the other way round. Until ...
0
votes
3answers
72 views

Find $19^{92} \pmod {92}$

How can I find $19^{92}\pmod{92}$? I am completely stumped. I thought of calculating $19^{92} \pmod{23}$ and $19^{92} \pmod{4}$.. ( because $23\cdot4 = 92$). But I don't know the modulo operation ...
3
votes
2answers
93 views

Backwards proof of Fermat's Little Theorem

$$\textrm{Let }p \in \mathbb{N}. \textrm{ Show that }\forall n \in \left \{ 1,2,...,p-1 \right \} \textrm{if } n^{p-1} \equiv 1 \mod p \Rightarrow p \in \mathbb{P}$$ This is basically Fermat's ...
1
vote
1answer
49 views

how to solve system of quadratic equations (mod N)

Given a two equations: $${(ax_1 + b)}^2 = c_1 \pmod N$$ $${(ax_2 + b)}^2 = c_2 \pmod N$$ $N=p.q$ $p$ and $q$ are large primes $x_1, x_2$ and $c_1, c_2$ are known Is it computationally feasible to ...
1
vote
1answer
31 views

Consider the number $N=2015^{2015}$. What is the remainder of $N$ when it is divided by $4$? $11$? $44$?

The question: Consider the number $N=2015^{2015}$. What is the remainder of $N$ when it is divided by $4$? $11$? $44$? I used a modulo calculator to get that the answer for $N$ mod $4$ is $3$, and ...
10
votes
3answers
95 views

Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$.

So the problem states: Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$. I was thinking about trying to prove this using the corollary to ...
2
votes
1answer
38 views

Multiple roots in $\mathbb{Z}_p$

Let f(x) ∈ $\mathbb{Z}$[x], a polynomial of degree n. Suppose f(x) has n distinct roots $a_1, ..., a_n$ ∈ $\mathbb{C}$. Now, with a given f(x), we call a prime p "bad" if f(x) has a ...
1
vote
0answers
64 views

$5^x \equiv 1520 \pmod {9797}$ [duplicate]

How do you solve this? What does mod mean and how will I solve it? I understand that it can be solved but how? 5 to some exponent equals the (mod of 9797) what is the answer to this?
1
vote
9answers
80 views

Find integers $m$ and $n$ such that $14m+13n=7$.

The Problem: Find integers $m$ and $n$ such that $14m+13n=7$. Where I Am: I understand how to do this problem when the number on the RHS is $1$, and I understand how to get solutions for $m$ and ...
3
votes
3answers
74 views

Calculate possible values of $a^4$ mod $120$.

Calculate possible values of $a^4$ mod $120$. I don't know how to solve this, what I did so far: $120=2^3\cdot3\cdot5$ $a^4 \equiv 0,1 \pmod {\!8}$ $a^4 \equiv 0,1 \pmod {\!3}$ $a^4 \equiv 0,1 ...
7
votes
1answer
86 views

Carmichael numbers of form $m^3+1$ and Ramanujan's $1729$

While researching for a post on tetranacci pseudoprimes I came across a list of Carmichael numbers, $$C_n = 561,\, 1105,\, 1729,\, 2465,\, 2821,\dots$$ Of course, Ramanujan's taxicab number $1729 = ...
2
votes
2answers
40 views

Question about working in modulo?

This question is in essence asking for understanding of a step in Fermats theorem done Group style. For any field the nonzero elements form a group under field multiplication. So let us take the ...
5
votes
4answers
105 views

What is $3^{43} \bmod {33}$?

I just took math final and one of the question was Find $3^{43}\bmod{33}$. So, I used Euler's function; $\phi(33)=20$. $3^{20}\equiv 1\pmod{\!33}$ By using this fact, I got $27$. One ...
1
vote
1answer
34 views

Prove that if $\{1^5,2^5,\ldots, (pq)^5\}$ is a complete residue system mod $pq$, then $\{1^5,2^5,\ldots,p^5\}$ is a complete residue system mod $p$.

Let $p,q\ge 2$ be coprime positive integers. Prove that if $\{1^5,2^5,\ldots, (pq)^5\}$ is a complete residue system mod $pq$, then $\{1^5,2^5,\ldots,p^5\}$ is a complete residue system mod $p$. ...
4
votes
1answer
85 views

Sum of elements of a finite Field

Let $F$ be a finite field and $i$ an integer. Calculate the sum of all the elements of $F$,each raised to the $i-th$ power. My approach so ...
2
votes
1answer
42 views

Proving consecutive quadratic residue modulo p [duplicate]

Let p be a prime with p > 7. Prove that there are at least two consecutive quadratic residues modulo p. [Hint: Think about what integers will always be quadratic residues modulo p when p ≥ 7.]
-1
votes
4answers
52 views

Last 2 digits of a product [closed]

What will be the last two digits of $25^{63} \cdot 63^{25}$? The answer is given as $25$ or $75$. What is the procedure to reach this answer?
1
vote
3answers
51 views

Why isn't Euler's theorem working to find the smallest $k$ such that $10^k \equiv 1 \pmod {\!9}$?

$10^k \equiv 1 \pmod {\!9}$ According to Euler's theorem and the Carmichael function, smallest $k$ is $\phi(9) = 6$, but clearly the smallest $k$ is $k=1$. What am I doing wrong?
0
votes
6answers
48 views

Finding the inverse of a number under a certain modulus

How does one get the inverse of 7 modulo 11? I know the answer is supposed to be 8, but have no idea how to reach or calculate that figure. Likewise, I have the same problem finding the inverse of 3 ...
-1
votes
2answers
57 views

$x^2 \equiv a$ mod p, $x^2 \equiv b$ mod p, and $x^2 \equiv ab$ mod p, prove either all three are solvable or exactly one

Let p be an odd prime and a, b ∈ Z with p doesn't divide a and a doesn't divide b. Prove that among the congruence's $x^2 \equiv a$ mod p, $x^2 \equiv b$ mod p, and $x^2 \equiv ab$ mod p, either all ...
4
votes
1answer
44 views

Way to calculate exponent in congruent equation

I want to solve $$ 5^{x} \equiv 21 \pmod {23} $$ Is there a way to get the $x$ without trial & error?
2
votes
2answers
116 views

If $ p $ is an odd prime and $ D $ an integer not divisible by $ p $, show that $ x^2 - y^2 \equiv D ~ (\text{mod} ~ p) $ has $ (p - 1) $ solutions.

I am supposed to have proved the following congruence identity: $$ 1^{n} + 2^{n} + \cdots + (p - 1)^{n} \equiv 0 ~ (\text{mod} ~ p). $$ This is apparently meant to help me solve the problem stated in ...
-2
votes
5answers
64 views

Solving $7a + 8 \equiv 5 \pmod{11}$ [closed]

Solve $7a + 8 \equiv 5 \pmod{11}$. I am having trouble answering this math problem. The final answer should work out to be $a = 9$ but I quite simply don't know to get that answer.
0
votes
1answer
33 views

Real numbers modulo $1$.

In teaching material of my professor I read "where $x_1,x_2,...,x_m$ are distinct real numbers modulo $1$". What is the definition of numbers modulo $1$? Intuitively I would say that there exist a ...
4
votes
6answers
162 views

(14^2014)^2014 mod 60 without a calculator

Calculate without a calculator: $\left (14^{2014} \right )^{2014} \mod 60$ I was trying to solve this with Euler's Theorem, but it turned out that the gcd of a and m wasn't 1. This was my ...
2
votes
2answers
42 views

Needing help finding the least nonnegative residue

$2^{47} \bmod 23$ $776^{79} \bmod 7$ $12347369^{3458} \bmod 19$ $5^{18} \bmod 13$ $23^{560} \bmod 561$ I really don't understand how to calculate the ones to powers. Could anyone explain how to ...
1
vote
3answers
45 views

Find the least nonnegative residue of $3^{1442}$ mod 700

So I have that $700=7\cdot2^2\cdot5^2$ and I got that $3^2\equiv1\pmod2$ so then $3^{1442}\equiv1\pmod2$ also $3^2\equiv1\pmod{2^2}$ so $3^{1442}\equiv1\pmod{2^2}$ which covers one of the divisors of ...
4
votes
0answers
57 views

Find all positive values for j,k,l such that j, k, l are positive integers and (j-k)|l, (k-l)|j, (l-j)|k.

Find all possible values of $j,k,l$ such that $j, k, l$ are positive integers and $(j-k)|l, (k-l)|j, (l-j)|k$. As I understand that using divisibility properties, it is possible to come to some ...
3
votes
5answers
101 views

How to find $2^{37} \bmod 77$?

Is there any quick way to find $2^{37} \bmod 77$? I have tried breaking it down into 2 components for example .. $2^{37} \bmod 7$ and $2^{37} \bmod 11$ but still no luck. Any ideas? Thanks
4
votes
2answers
127 views

Euler Fermat with double exponent [duplicate]

I have to calculate $$ 3^{{2014}^{2014}} \pmod {98} $$ (without calculus). I want to do this by using Euler/Fermat. What I already have is that the $\gcd(3, 98) = 1$ so I know that I can use the ...
0
votes
2answers
54 views

Find the least nonnegative residue of $68^{105} \pmod{13}$.

I did a problem before this, which was finding the least nonnegative residue of $2^{204} \pmod{13}$. Because $2^{6} ≡ 1 \pmod{13}$, I said that $(2^{6})^{34}≡1^{34} \pmod{13}$, and so I concluded that ...
3
votes
5answers
66 views

The residue of $9^{56}\pmod{100}$

How can I complete the following problem using modular arithmetic? Find the last two digits of $9^{56}$. I get to the point where I have $729^{18} \times 9^2 \pmod{100}$. What should I do from ...
2
votes
2answers
92 views

Numbers of the form $5 \cdot 2^{n}-1$ divisible by $3^k$ for large values of $k$

Let $n_k$ be the smallest integer such that $5 \cdot 2^{n_k}-1$ is divisble by $3^k$ where $k$ is a positive integer. Can one say something about the growth of $n_k$ with respect to $k$ ? Is it ...
2
votes
0answers
33 views

Is the multiplication modulo $p$ for polynomials well-defined?

Is the multiplication modulo $p$ for polynomials well-defined ? I mean let $g,h\in\mathbb Z[x]$ and let $\bar g$ be the polynomial obtained from $g$ by reducing all the coefficients of $g$ modulo ...
1
vote
1answer
54 views

How many solutions to $x^d\equiv a\pmod {p}$?

If $\gcd(d,p-1) = 1$, there is a unique solution to $x^d \equiv a \pmod p$. If $\gcd(d,p-1) > 1$, there are exactly $d$ solutions to $x^d\equiv a\pmod p$. $p$ prime, $d\ge 1$, ...
1
vote
1answer
36 views

Grid Problem Proof

I have a 2x2 grid square say, I can fit a shape like this: Such that there is one missing square. I can arrange this in any way so that the missing square can be located anywhere. I can do ...
6
votes
1answer
124 views

How to prove that $a=z^{p}$ for some $z \in \mathbb{Z_{+}}$?

Claim : If for a positive, composite integer $a$ and an odd prime $p$, such that $\gcd(a,p)=1$, we are given $$ a^{p^{n-2}(p-1)} \equiv 1 \pmod {p^n} \ \forall \ n \geq 2 \ \ ;\ ...
1
vote
1answer
29 views

If $p$ is an odd prime with $(p - 1)/2$ primitive roots, is $p$ a Fermat prime?

If $p$ is an odd prime and there are $(p - 1)/2$ primitive roots modulo $p$, then is $p = 2^k + 1$ for some nonnegative integer $k$? This is the converse of a statement that I have already ...
0
votes
2answers
27 views

Should the order of $a^k$ be $h/k$ as opposed to $h/(h,k)$?

Previously shown: Let $m\in\mathbb{N}$ and $a\in\mathbb{Z}$ s.t. $(a,m)=1$. Then the order $d$ of $a$ modulo $m$ exists and $d\mid\phi(m)$. Moreover, whenever $a^k\equiv 1\pmod{m}$, one has $d\mid ...