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

4
votes
7answers
142 views

Prove: “The cube of any number not a multiple of 7, will equal one more or one less than a multiple of 7”

Yeah so I'm kind of stuck on this problem, and I have two questions. 1. Is there a way to define a number mathematically so that it cannot be a multiple of $7$? I know $7k+1,\ 7k+2,\ 7k+3,\ \cdots$...
1
vote
1answer
627 views

Solving a non-linear congruence

How can we solve for $x$, knowing the integer $n$ and the real numbers $a$ and $b$, the following non-linear congruence: $(x+a)^2=-b\pmod{n}$ Specifically in this example: $(x+\frac{1}{2})^2=-\frac{...
3
votes
5answers
125 views

How to find last two digits of $2^{2016}$

What should the 'efficient' way of finding the last two digits of $2^{2016}$ be? The way I found them was by multiplying the powers of $2$ because $2016=1024+512+256+128+64+32$. I heard that one way ...
1
vote
0answers
12 views

Orders of elements in multiplicative groups of fields with positive characteristic

Suppose that $k$ is a field with positive characteristic $p$. I want to show that for each $x\in k$ the set $\{x^n\colon n\in \mathbb{N}\}$ is finite. My intuition tells me that I should use Fermat's ...
7
votes
2answers
450 views

How to solve congruence $x^y = a \pmod p$?

I'm having trouble solving this congruence: $$x^{114} \equiv 13 \pmod {29}.$$ I thought that it made sense to try to solve it using this idea: "Suppose you want to solve the congruence $ x^y \equiv a \...
1
vote
1answer
18 views

Generate Sieve of Eratosthenes without “sieve” (generate prime set in interval)

How do I generate a list of primes based on the Sieve of Eratosthenes? I mean by excluding the divisible numbers beforehand, which is tricky for large numbers. I am an number theory amateur, but was ...
6
votes
1answer
306 views
+100

Conjecture about primes and the factorial

Below $0\notin\mathbb N$. Further corrected conjecture: For all prime numbers $p>5$ there exist a prime number $q<p$ such that $q\equiv m!\!\pmod p$, $2<m<p$. or Given a prime ...
25
votes
7answers
3k views

How do I compute $a^b\,\bmod c$ by hand?

How do I efficiently compute $a^b\,\bmod c$: When $b$ is huge, for instance $5^{844325}\,\bmod 21$? When $b$ is less than $c$ but it would still be a lot of work to multiply $a$ by itself $b$ times, ...
1
vote
1answer
90 views

Find the remainder using Fermat's little theorem when $5^{119}$ is divided by $59$?

How to find the remainder using Fermat's little theorem? Fermat's little theorem states that if $p$ is prime and $\operatorname{gcd}(a,p)=1$,then $a^{p-1} -1$ is a multiple of $p$. For example, $p=...
3
votes
2answers
110 views

Closed-Form Modular Arithmetic

Is there a way to define modulo division (or functions of modular arithmetic in general) as superposition of (elementary?) functions? For example, the multiplication is first introduced as summation,...
7
votes
2answers
267 views

Fermat's Little Theorem and Euler's Theorem

I'm having trouble understanding clever applications of Fermat's Little Theorem and its generalization, Euler's Theorem. I already understand the derivation of both, but I can't think of ways to use ...
2
votes
5answers
87 views

How to find remainder when $ 975^{40153}$ is divided by $14$? [duplicate]

I still find tricky this kind of problems. I tried to do solve it by factoring $14$ in $2*7$. Then, with Fermat's Little Theorem, I find that: $975^6\equiv 1\pmod 7$ $975^1\equiv 1\pmod 2$ How can ...
0
votes
1answer
30 views

Counting number of cosets

Let $G = \big(\mathbb{Z}/n\mathbb{Z})^*$, that is the multiplicative group modulo $n$. For some $d$ coprime to $n$, let $H$ be a subgroup of $G$ generated by $d$. As $G$ is abelian, $H$ is normal in $...
1
vote
4answers
56 views

If the sum of two $p$th powers is divisible by $p$, then it is divisible by $p^2$

If $p > 2$ is a prime and $p | (x^p + y^p)$, then show that $p^2 | (x^p + y^p)$ I have been stuck on this problem for a while now. (Though my textbook is prone to mistakes so the original ...
0
votes
1answer
29 views

What is (a mod n) mod n?

I have an equation such as (a + b) mod n which is nothing but (a mod n + b mod n) mod n according to this. Now, I know that b mod n is 0 which results in (a mod n) mod n. Is this equivalent to a ...
2
votes
0answers
15 views

Solving Modular Equation

Let $d$ and $n$ be coprime. What is the smallest positive solution for x in the equation: $$d^x \equiv 1 \mod n$$ This value must depend on both $d$ and $n$. We know that the maximum value for it is ...
3
votes
1answer
91 views

Find last 5 significant digits of 2017!

Since there are less powers of $5$ than of $2$ and since $10 = 2 \cdot 5$, I counted the number of zeros in $2017!$: $\left \lfloor{ \frac{2017}{5^1}}\right \rfloor + \left \lfloor{ \frac{2017}{5^2}}\...
0
votes
1answer
16 views

Solving for exponent in modular arithmetic equation

Let there be two numbers $a$ and $d$ such that GCD(a,d) = 1. For a given value of $k$, how many solutions are there for: $$d^xk = k \mod a$$ We know that if GCD(a,k) = 1, then there is only one ...
2
votes
6answers
76 views
1
vote
3answers
25 views

$a\equiv b\pmod{n}\iff a/x\equiv b/x\pmod{n/\gcd(x,n)}$ for integers $a,b,x~(x\neq 0)$ and $n\in\Bbb Z^+$?

I'm trying to prove/disprove the following: If $a,b,x$ be three integers (where $x\neq 0$) such that $x\mid a,b$ and $n$ be a positive integer, then the following congruence holds: $$a\equiv ...
1
vote
1answer
60 views

Conjecture concerning modular arithmetic

Below $0\notin\mathbb N$. I want a proof or a counter-example of the following (corrected) conjecture: Suppose $p$ is the smallest prime dividing $n\in\mathbb N$ and suppose $kn+ap=m!$, where $...
0
votes
0answers
8 views

How to keep result of calculation to be in particular range?

I have data as :- Group A Element A score(3) Element B score(1) score 4/2 ...
0
votes
2answers
36 views

How to apply Chinese Reminder Theorem to this congruence system?

\begin{align*} 17x & \equiv -15 \pmod{5}\\ -11x & \equiv 5 \pmod{3}\\ 23x & \equiv 15 \pmod{7} \end{align*} $5$, $3$, $7$ are coprime, so the system has solution mod $105$. I'm not sure ...
1
vote
0answers
51 views

No square has a decimal expansion ending in 79

Show that no square number has a decimal ending in 79. More generally, find all possible two-digit endings for squares. Let any digit number ending at 79 be represented as $$a_nx^n+.....+7x+9$$ Plug ...
11
votes
2answers
379 views

Are integers mod n a unique factorization domain?

I am trying to learn abstract algebra from scratch, jolly stuff, but in the process of doing so this puzzles me: Having a ring of integers mod $n$, where $n=pq$ is composite, as I understand we have ...
5
votes
8answers
89 views

How to show $(3^ {2n} - 1) \equiv 0 \mod 8$

How can I show that $$3^{2n}-1 \equiv 0 \pmod 8$$ is true? What kind of method should I approach this problem with? I was thinking induction but but chapter isn't about induction so need some help......
1
vote
1answer
28 views

Remainder modulo matrices.

Is it possible to have a consistent definition of $A\bmod_{left} B$ that respects matrix multiplication from left where $A$ and $B$ are two square matrices with non-negative entries? Is there a ...
2
votes
0answers
39 views

Proof of the Ribet's theorem

My question is very simple : My goal is to read a proof the proof of the epsilon conjecture proven by Ken Ribet (1986) which is an ingredient of the proof of the Fermat Last Theorem (I want the ...
0
votes
4answers
10k views

Calculator model with mod function?

I'm wondering does anyone know of a scientific calculator with a mod function? In C# this is shown as follows (just in case there are any other mods that a mathematical non-savant such as myself ...
1
vote
0answers
12 views

What are good parameters for an $ax+b \pmod{2^L}$ hash with distinct first n bits of the first $2^n$ inputs?

I'm hashing 64 bit integers via $ax+b \pmod{2^{64}}$. Good parameters mean that, given an $1 \leq n \leq 64$, the first $n$ bits of the first $2^n$ inputs are distinct. How should I chose $a$ and $b$ ...
0
votes
1answer
34 views

Calculating the last digit of exponent

I need to calculate the last digit of $723^n$.(For every positive integer $n$). If it was to calculate the last digit of $a^b$ when I know the value of $a$ and $b$,then it was easy- for example,If I ...
-1
votes
0answers
55 views

A square-related question in modular arithmetic…

Let $n$ and $k<\frac{n}{2}$ be integers with $4|n$. Find the pairs $(n,k)$, such that: $i(k-1)\not\equiv\frac{n}{2}\pmod n$, for all $i\in\mathbb{Z}_n$, or $i(k+1)\not\equiv\frac{n}{2}\pmod n$, ...
0
votes
4answers
85 views

Why k should be odd? [duplicate]

My teacher once said, for any positive number $\ n, $ $\ n^k - 1 $ would always have $\ n-1 $ as a factor for all positive odd values of $\ k $. Could anyone tell me the proof? I have written my ...
2
votes
0answers
51 views

Finding solutions in modulo

If I know $x$ modulo m and n, then under what conditions on m,n and p will i necessarily know $x$ modulo p? My initial guess is only in trivial cases, i.e. p is a multiple of m or n, but i cant seem ...
3
votes
4answers
78 views

Find $6^{1000} \mod 23$ [duplicate]

Find $6^{1000} \mod 23 $ Having just studied Fermat's theorem I've applied $6^{22}\equiv 1 \mod 23 $, but now I am quite clueless on the best way to proceed. This is what I've tried: Raising ...
1
vote
3answers
300 views

Find the remainder $4444^{4444}$ when divided by 9 [duplicate]

Find the remainder $4444^{4444}$ when divided by 9 When a number is divisible by 9 the possible remainder are $0, 1, 2,3, 4,5,6,7,8$ we know that $0$ is not a possible answer. My friend told me the ...
4
votes
5answers
172 views

Find $3^{333} + 7^{777}\pmod{ 50}$

As title say, I need to find remainder of these to numbers. I know that here is plenty of similar questions, but non of these gives me right explanation. I always get stuck at some point (mostly right ...
-1
votes
2answers
37 views

Given $(c -x) % (n - 1) == 0$ for some $x$, how do I find a suitable $x$?

Given $(c - x)$ $mod$ $(n - 1)$ $= 0$ for some $x$, how do I find a suitable $x$? $c$ = constant $x \ge 2$ $n - 1$ = constant
0
votes
4answers
74 views

How to approximate

I was reading a book and saw this approximation $(1 - 10^{-3})^{1023} \approx 2^{-1.476}$ I am wondering how it is calculated.
4
votes
1answer
77 views

Pattern in numbers

I bumped into this mathematical calculation while driving my car. With lot of traffic jams and lot of time to kill, I did some scrambling of the registration numbers of the cars in front of me. I ...
1
vote
1answer
42 views

Minimizing a sum given variables

I have this expression $$ax - b\left\lfloor\frac{cx}{m}\right\rfloor$$ Variables $a, b, c, m$ are known/given positive integers, and $x$ is an unknown integer with bounds $1 \leq x \leq m-1$. I ...
17
votes
0answers
236 views

Finding primes so that $x^p+y^p=z^p$ is unsolvable in the p-adic units

On my number theory exam yesterday, we had the following interesting problem related to Fermat's last theorem: Suppose $p>2$ is a prime. Show that $x^p+y^p=z^p$ has a solution in $\mathbb{Z}_p^{\...
0
votes
1answer
476 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
1
vote
1answer
28 views

How many more legs than seats are in the leftover inventory (use modular-arithmetic)?

I have difficult with this problem, and appreciate any help. The Seats R Us factory produces chairs with four legs and stools with three legs. The seats and legs are the same for both chairs and ...
2
votes
2answers
37 views

Find two integers between 1 and 100

Can anyone help me with this? Thank you very much! Problem: Find two integers between 1 and 100 such that for each: a) if you divide by 4, the remainder is 3; b) if you divide by 3, the remainder ...
1
vote
1answer
33 views

What is the value of $N$ in a three-digit number $1N1$?

I don't know how to solve this problem. This is as far as I can go. $$\frac{1N1}{N}=2N+5$$ Then what should I do from there? Any help is highly appreciated. If a three-digit number of the form $...
2
votes
4answers
110 views

Is this possible to solve through algebra?

$$150 \equiv 17 \mod x, \qquad 100 \equiv 5 \mod x $$ Solve the simultaneous equation? Is this even a simultaneous equation? How do I find the value of $x$ too? I was doing a question and came up ...
3
votes
1answer
27 views

Determine the quadratic character of $293 \bmod 379$.

Determine the quadratic character of 293 mod 379. Did several other problems like this with 3, 5, 60, -1 and 307 all mod 379 but still having a tough time with this problem. I can post up work from ...
0
votes
1answer
32 views

Solving algebraic equations with modulus [closed]

How do I solve for 'b' given: $1 \equiv a\pmod{2} \\ a=\frac{b-1}{3}$
1
vote
1answer
35 views

Is there an integer z such that $255z\equiv 7\pmod {633}$?

I used the extended euclidean algorithm to "Find integers x and y such that $633x + 255y = 6$, or explain why none exist." And found that $6x = -58$ and $y = 144$. Now I'm stuck on the follow up ...