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

2
votes
1answer
381 views

What software can calculate the order of $b \mod p$, where $p$ is a large prime?

I wasn't sure where to ask this, but Mathematics seems better than StackOverflow or Programmers. I have no background whatsoever in number theory, and I need to find software that can calculate the ...
1
vote
2answers
81 views

Show that for any uneven $n$ it follows that $n^2 \equiv 1 \mod 8$ and for uneven primes $p\neq 3$ we have $p^2 \equiv 1\mod 24$.

Show that for any uneven $n$ it follows that $n^2 \equiv 1 \mod 8$ and for uneven primes $p\neq 3$ we have $p^2 \equiv 1\mod 24$. My workings so far: I proceeded by induction. Obviously $1^2 \equiv 1 ...
2
votes
1answer
396 views

Computing $\bmod$s with large exponents by paper and pencil using Fermat's Little Theorem.

I'm having a bit of trouble computing $\bmod{mod}$s of large numbers using Fermat's Little Theorem. For example, how would you compute $7^{435627650}\mod 13$? The solution given is $435627650\mod ...
3
votes
4answers
84 views

Solving for Modular arithmetic

Solve the equation $38z\equiv 21 \pmod {71}$ for z. Little confused by the questions. My attempt is: $38 \odot z = 21.$ Then find the inverse of 38 from mod 71 and multiply both sides. Lastly, take ...
7
votes
2answers
191 views

Does there always exist an odd number of elements?

Given a nonzero integer $k$, does there always exist a positive integer $n$ such that there are exactly an odd number of elements $i\in\{0,1,...,n-1\}$ with $\frac{2^n-1}4 < 2^ik \mod{2^n-1} < ...
1
vote
1answer
85 views

Does $a \mid bc$ imply $\frac{a}{(a,b)} \mid c$?

If $a \mid bc$, then does $\frac{a}{(a,b)} \mid c$? I doubt anybody here is industrious enough to show this via a diagram, but who knows.
3
votes
1answer
62 views

Primitve roots and congruences?

Let $p$ be an odd prime. Show that the congruence $x^4$$\equiv -1\text{ (mod }p\text{)}\ $ has a solution if and only if $p$ is of the form $8k+1$. Here is what I did Suppose that $x^4$$\equiv ...
-1
votes
5answers
111 views

$(a,m) = (b,m) = 1 \overset{?}{\implies} (ab,m) = 1$

In words, is this saying that since $a$ shares no common prime factors with $m$ and $b$ shares no common prime factors with $m$ too, then of course the product of $a$ and $b$ wouldn't either!?
3
votes
6answers
144 views

$11$ divides $10a + b$ $\Leftrightarrow$ $11$ divides $a − b$

Problem So, I am to show that $11$ divides $10a + b$ $\Leftrightarrow$ $11$ divides $a − b$. Attempt This is a useful proposition given by the book: Proposition 12. $11$ divides a ...
-2
votes
1answer
108 views

Finding a primitive root modulo $13$ [duplicate]

Find a primitive root modulo each of the following integers. a) $13$ My TA said we are not going to go over this. We did not go over the topic. It seems like something good to know though. ...
1
vote
2answers
167 views

Determine number of squares in progressively decreasing size that can be carved out of a rectangle

How many squares in progressively decreasing size can be created from a rectangle of dimension $a\;X\;b$ For example, consider a rectangle of dimension $3\;X\;8$ As you can see, the biggest square ...
1
vote
1answer
233 views

Finding a primitive root modulo $11^2$

Find a primitive root modulo each of the following moduli: a) $11^2$ My TA said he is not going to go over this so do not worry about it. He said you can try this if you want but he would ...
2
votes
6answers
898 views

Finding the remainder when $2^{100}+3^{100}+4^{100}+5^{100}$ is divided by $7$

Find the remainder when $2^{100}+3^{100}+4^{100}+5^{100}$ is divided by $7$. Please brief about the concept behind this to solve such problems. Thanks.
0
votes
1answer
42 views

Is the “least non-negative residue” of $b^p \pmod{m}$ just $b^p \pmod{m}$?

I'm just wondering if the "least non-negative residue" of $b^p \pmod{m}$ is just $b^p \pmod{m}$ itself. What is the "least non-negative residue"? How is it found? Is this how it is found? Just by ...
-2
votes
1answer
108 views

Modular Arithmetic: Least Non-negative Residues

I am to compute the least non-negative residue of $4^n \pmod{9}$ for $n = 1, 2, 3, 4, 5, \dots$ I must also prove that $6 · 4^n ≡ 6 \pmod{9}$ for every $n > 0$.
0
votes
4answers
168 views

Calculations by Hand

Find the least non-negative residue of: (i) $5^{18}$ mod $11$ (ii) $68^{105}$ mod $7$ (iii) $4^{47}$ mod $12$ (iv) $66^{75}$ mod $19$ C++ code failed... I'm trying to do by hand now. Maple has ...
2
votes
1answer
57 views

$15a ≡ ca \pmod{25}$, then $15 ≡ c \pmod{25}$

For which numbers $a$ is it true that if $15a ≡ ca \pmod{25}$, then $15 ≡ c \pmod{25}$? I know that this means that $a\frac{15-c}{25}=k_1\in \mathbb{Z}$ and $\frac{15-c}{25}=k_2\in \mathbb{Z}$, but ...
-2
votes
4answers
96 views

One Number in the Set $\{0,1,…,m−1\}$

Let $m$ be a natural number $>1$. Every natural number is congruent modulo $m$ to exactly one number in the set $\{0,1,...,m−1\}$. Where can I find a concrete proof of this theorem?
0
votes
1answer
45 views

Probability about inverse of modulo $n$

If $\gcd(a,n)=1$, then the solution of $a \cdot x \equiv 1 \bmod n $ is $x \equiv a^{\varphi(n)-1} \bmod n$. I want to know the probability of $Pr( (x\bmod n)> n/2)$?
1
vote
2answers
36 views

Simple Filter Function

I'm trying to find a function $f(x)$ when $x>1$ which gives $0$ when $x=1$ and $200$ for all positive integers $x>1$. i.e. $f(1) = 0 $ $f(2) = 200$ $f(3) = 200 $ $f(4) = 200$ and etc.. ...
2
votes
2answers
85 views

Proving if $a_1\equiv b_1\pmod{n}$ and $a_2\equiv b_2\pmod{n}$ then we have $a_1+a_2\equiv b_1+b_2\pmod{n}$.

How can I prove if $a_1\equiv b_1\pmod{n}$ and $a_2\equiv b_2\pmod{n}$ then we have $a_1+a_2\equiv b_1+b_2\pmod{n}$? I have tried several ideas I've found online but don't really understand them. Is ...
1
vote
1answer
60 views

Formula for working out an ID number by given set of coordinates

I'm designing an online game and having a bit of a mental block coding the navigation system. It's designed on a 2 dimensional grid, each cell has an ID 0...n, n being the total number of cells in the ...
3
votes
2answers
153 views

Help with proof of showing idempotents in set of Integers Modulo a prime power are $0$ and $1$

I was reading online for a project I'm currently doing and came across the following claim and proof. The statement would be useful to me, and although I've spent a long time looking at it there's ...
2
votes
5answers
117 views

How to show that $p!+1\equiv 1 \mod k$

I am a non mathematician who is taking a self study class in number theory. I was wondering how to formally prove the following: Let $p$ be a prime number. How can I show that $$p!+1\equiv 1 \mod k$$ ...
3
votes
2answers
73 views

Is $\sum\limits^n_{k=0}\frac{(y-0)(y-1)\cdots(y-n)}{y-k} \equiv 0 \pmod{n+1}$?

Let $n$ be a positive integer such that $n+1$ is a prime power. That is, to illustrate $n+1$ is $9$ or $25$. Prove that $$\sum^n_{k=0}\frac{(y-0)(y-1)\cdots(y-n)}{y-k} \equiv 0 \pmod{n+1}.$$ Hint: I ...
3
votes
6answers
3k views

Arithmetic with Large modular exponent and repeated squaring, such as $10^{221}$ (mod $13$).

How would you compute $10^{221}$ mod $13$ by repeated squaring? I just started studying discrete mathematics and I think this would help me in the future. I looked at this example Computing large ...
1
vote
3answers
281 views

Computing large modular numbers

How do you compute large modular arithmetic such as $8^{128}$ $mod$ $100$ or $10^{111}$ $mod$ $137$ or $3^{100}$ mod $17$? I know that one way is repeated squaring. For the first one, my book says 16, ...
3
votes
2answers
65 views

Modular Exponentiation

Give numbers $x,y,z$ such that $y \equiv z \pmod{5}$ but $x^y \not\equiv x^z \pmod{5}$ I'm just learning modular arithmetic and this questions has me puzzled. Any help with explanation would be ...
3
votes
3answers
263 views

What will be the units digit of $7777^{8888}$?

What will be the units digit of $7777$ raised to the power of $8888$ ? Can someone do the math with explaining the fact "units digit of $7777$ raised to the power of $8888$"?
2
votes
3answers
102 views

Solve for $x$: $4x = 6~(\mod 5)$

Solve for $x$: $4x = 6(mod~5)$ Here is my solution: From the definition of modulus, we can write the above as $ \large\frac{4x-6}{5} = \small k$, where $k$ is the remainder resulting from ...
3
votes
3answers
327 views

Find the values of $p$ such that $\left( \frac{7}{p} \right )= 1$ (Legendre Symbol)

Show that if $p$ is an odd prime coprime to $7$, then $\left( \frac{7}{p} \right) = 1$ if and only if $p \equiv \pm 1, \pm 3,$ or $\pm 9 \pmod{28}$. HINT: If $p$ is an odd prime, determine which ...
2
votes
2answers
282 views

Miller-Rabin Primality Test

I am trying to work out the potential primality of 341 using the Miller-Rabin algorithm. Below is as far as I get, I'm not really sure where to go from there. I believe I am supposed to use modular ...
1
vote
1answer
79 views

Modular Arithmetic: $ 291-118 \pmod 4\;$?

How do you work out: the value of $ 291-118 \pmod 4\;$? Thanks
4
votes
2answers
131 views

“Tricky” wording on Congruence Modulo Question?

I'm asked for all possible values, but I can only see one. The question on my practice exam reads: Consider the equivalence class [3] for the equivalence relation "congruence modulo $7$" on $\Bbb Z$. ...
1
vote
1answer
29 views

Order of $(F_{k-1}$ mod $p)$ in $F_p^*$ for primefactor $p$ of fermat number $F_k$.

Let $p$ be a primefactor of $F_k = 2^{2^k} + 1$. I proved that $(2$ mod $ p)$ has order $2^{k+1}$ in $F_p^*$. Suppose that $k \geq 2$. How does it follow that $(F_{k-1}$ mod $p)$ has order $2^{k+2}$ ...
1
vote
0answers
109 views

Last 2 digits of modular exponentiation

Is there any shortcut way to find the last two decimal digits of a modular exponentiation (base always is a single digit number) without doing square and multiply? As an example in $$2^{100001} ...
4
votes
5answers
7k views

Finding the last digit in a large exponent.

I'm practicing for my algebra exam but I stumbled on a question I don't know how to solve. Let $N = 3^{729}$. What is the last digit of $N$? The example answer says Since gcd $(3, 10) = 1$, ...
3
votes
1answer
78 views

Find all integer solutions of $35x^{31} + 33x^{25} + 19x^{21} \equiv 1 \pmod{ 55}$

Find set of all integers x for which the following holds: $35x^{31} + 33x^{25} + 19x^{21} \equiv 1 \pmod {55}$ Since $55 = 5\cdot 11$, simultaneous congruences: $35x^{31} + 33x^{25} + 19x^{21} ...
1
vote
2answers
51 views

Simple modular arithmetic question

Can someone please give a clear explanation on how from $(41)(59)x\equiv x\pmod {78}$ and $(41)(59)x\equiv 123\pmod {78}$ we get $x\equiv 123\pmod {78}$?
1
vote
2answers
137 views

Why is a prime number needed for the Diffie-Hellman key exchange? (modular arithmetic)

I'm writing a cryptography essay, and am wondering why you need a prime number for the deffie-hellman key exchange? Any help would be appreciated :) this is a link to a previous post which quickly ...
3
votes
2answers
233 views

$\mathbb Z_p^*$ is a group.

I'm trying to prove that $\mathbb Z_p^*$ ($p$ prime) is a group using the Fermat's little theorem to show that every element is invertible. Thus using the Fermat's little theorem, for each $a\in ...
2
votes
3answers
100 views

Congruence Problem

Given $a,m \in\mathbb{N}$ with $gcd(a,m)=1$, let $x_1\in\mathbb{N}$ be a solution to the congruence $ax\equiv1\pmod m$. For each integer $k\ge1$, number is defined as $x_k:=\frac{1}{a}(1-(1-ax_1)^k]$. ...
4
votes
1answer
167 views

Using Fermats Little Theorem to show $2^{17} -1$ is prime

Show that $n = 2^{17} - 1$ is prime by using Fermat's Little Theorem $2^{p-1} \equiv 1 \mod p$ for any $p$ dividing $n$. I said, that by FLT, we get $2^{16} \equiv 1 \mod 17$, and we can see that ...
0
votes
1answer
59 views

Number Theory Proof Need Logic Checked

I'm working on the following problem: Show that if $x^{p} + y^{p} = z^{p}$, then $p \space | \space (x + y -z)$ So far my proof looks something like this: Suppose $p \nmid \space (x+y-z)$ ...
0
votes
3answers
95 views

Modulo number multiplied by constant

I am proving that for any integers $a,b$, it is impossible to write $a^2 - 5b^2 \equiv 2 \mod 4$. The first thing I have said is to assume $a,b$ are both even. So I have said $$a,b \equiv 0 \, \, ...
4
votes
6answers
115 views

Prove $7|x^2+y^2$ iff $7|x$ and $7|y$

The question is basically in the title: Prove $7|x^2+y^2$ iff $7|x$ and $7|y$ I get how to do it from $7|x$ and $7|y$ to $7|x^2+y^2$, but not the other way around. Help is appreciated! Thanks.
0
votes
1answer
827 views

How can you find large powers modulo n?

I am following an example in my book as follows: Find 7^64 mod 120. Note: (7,120) = 1 and φ(120) = 32, so 7^64 ≡ 7^0 ≡ 1 mod 120. This part I understand. It's ...
3
votes
1answer
1k views

Prove the converse of Wilson's Theorem

... namely that if $n > 1$ and $(n − 1)!\equiv−1\pmod{n}$, then $n$ is prime. This is for a number theory class I'm in at Penn State. My idea is to follow accordingly, but I can't get it ...
3
votes
3answers
220 views

The Chinese Remainder Theorem

I'm trying to do some questions on the Chinese Remainder Theorem, I've being reading the Wikipedia explanation but I still don't get it. Can someone explain it to me, please? Here is the question I'm ...
6
votes
3answers
188 views

Aut $\mathbb Z_p\simeq \mathbb Z_{p-1}$

I'm trying to prove that Aut $\mathbb Z_p\simeq \mathbb Z_{p-1}$ (p prime). I know that Aut $\mathbb Z_p$ has $p-1$ elements because $\mathbb Z_p$ has $p-1$ possiblities of generators, so intuitively ...