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

Hypothetical equation (modulo a power of two) and the value [duplicate]

We have hypothetical equation: $2^{b} \% k = z$. Assume that we know $z$, $b$ and $k$. So everything! We want to know only if the above equation is true. I do not want to use the exponentiation ...
1
vote
1answer
35 views

Primitive 18-th root of unity problem involving congruences.

I have some doubts about this following problem, if you can please try to answer the congruence step: Let $ \omega$ be a primitive 18-th root of unity. Find $ n \in \mathbb Z$ such that: $ \omega^n =...
2
votes
4answers
46 views

What constitutes a proof of congruence in modular arithmetic?

In this problem, don’t use a calculator. The answers can be derived without doing much computation, try to find these simple solutions. (a) $4 + 5 + 6 ≡ 0 \pmod {5}$ My professor gave me some ...
1
vote
1answer
24 views

How to calculate $(n^{-1})\%(p^a)$ for prime $p$?

I actually needed to calculate $(a/b)\%m$ when $m$ is not prime. Here is what I have done so far. $(a/b)\%m = (a* \text{modinv}(b))\%m$, I can calculate mod inverse only if $m$ and $b$ are co-primes. ...
0
votes
0answers
11 views

Obtaining a decimal from Modular multiplicative inverse [closed]

im having some trouble understanding how to calculate the value of a large integer to the power of a negative exponent. i have implemented: ax = 1 (mod m) for: <...
0
votes
1answer
24 views

Two different remainders for same expression

$$\frac{n! + 1}{n} = (n-1)! + \frac{1}{n}$$ The remainder is $\frac{1}{n}$ $$n! + 1 \equiv 1 \cdot 2 \cdot 3 \cdot \dotsc (n-1) \cdot 0 + 1 \equiv 1 \mod n$$ The remainder is $1$ What is going on? ...
0
votes
1answer
41 views

Proving the equivalence between two congruences.

According to this answer (and the modular arithmetic theory), $ax\equiv ay \pmod{n} \iff x\equiv y \pmod{n}$, if $a$ and $n$ are relatively prime. I tried to prove the forward implication but reached ...
9
votes
8answers
2k views

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. 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
0answers
15 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 ...
3
votes
5answers
144 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
1answer
23 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 ...
7
votes
2answers
287 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 ...
0
votes
1answer
38 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 $...
2
votes
5answers
88 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
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 ...
2
votes
2answers
140 views
+50

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}}\...
2
votes
6answers
77 views

How to find the reminder when $982^{40167}$ is divided by 15?

I probably have to use Euler's function but I'm not sure how.
1
vote
3answers
29 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
73 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
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 ...
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 ...
8
votes
1answer
442 views

Conjecture about primes and the factorial: for all primes $p>5$, must there exist a prime $q<p$ such that $q\equiv m!\pmod p$ for some $2<m<p$?

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 ...
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 ...
0
votes
2answers
38 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 ...
2
votes
0answers
50 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 ...
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 ...
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
35 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 ...
0
votes
4answers
86 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
55 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 ...
4
votes
1answer
80 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 ...
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.
1
vote
1answer
29 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
39 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
34 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 $...
-1
votes
2answers
38 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
2
votes
4answers
113 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 ...
0
votes
1answer
33 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 ...
1
vote
0answers
42 views

Use modular-arithmetic to solve a scheduling problem

Can anyone help me with this? I know the problem is related to mod, but I don't know how to solve it using modular-arithmetic. Three professors start to teach math on the first Monday, Tuesday, ...
0
votes
1answer
56 views

Alternate way of showing infinitude of primes of the form $4m+1$

I would like to know if my approach is valid. I want to show that there are infinitely many primes of the form $4m+1$. Assume the contrary, and denote each of these primes by $p_{i}$ with $i \in \{1,...
0
votes
2answers
20 views

Number of solutions for $a$ of $x^2\equiv a \pmod3$

Find the all the numbers $a$ such that for $x^2\equiv a \pmod3$ there is: A. exactly one solution. B. two solutions. C. three solutions. D. no solutions. My attempt: $$1^2\...
1
vote
2answers
60 views

Find the last digit of $66^5$

Find the last digit of $66^5$. This is how I solved the problem: $66^5=6^5*11^5$ (mod 10) = $6^5*1^5$ (mod 10). I have two questions. First, what is wrong with my method? I get different answer from ...
2
votes
4answers
65 views

Solve $x^2+x+1\equiv0\pmod5$

Solve: $$x^2+x+1\equiv0\pmod5$$ My attempt: Our proffesor told us that if we have $ax^2+bx+c\equiv\pmod p$ we need to multiply by $4a$, to get form of $(\text{ something})^2\equiv D\pmod p$. $...
2
votes
4answers
93 views

how to solve $x^{113}\equiv 2 \pmod{143}$

I need to solve $x^{113} \equiv 2 \pmod{143}$ $$143 = 13 \times 11$$ I know that it equals to $x^{113}\equiv 2 \pmod{13}$ and $x^{113}\equiv 2 \pmod{11}$ By Fermat I got 1) $x^{5} \equiv 2 \pmod{...
2
votes
4answers
71 views

Find smallest $x$ such that $x=59 \pmod {60}$ and $x=1 \pmod 7$

Is a simple way to solve the problem? The method I used is to list all numbers from equation (1) and then see which one give remainder $1$ when divided by $7$. This doesn't seems a very smart way. ...
1
vote
0answers
48 views

How to solve a modular inequality with optimization?

I have this: $x\le y$ $ y\lt m$ $x^2\mod m < y$ $y$ and $m$ are given. I am trying to maximize the value of $x$. Any advice on how to approach this?
2
votes
1answer
269 views

Remainder when dividing $13^{3530}$ with $12348$ [duplicate]

Find the remainder when dividing $13^{3530}$ with $12348$. How do I solve these type of exercises? I know there's some algorithm for solving them, I just haven't found a concrete example. Could ...
18
votes
0answers
247 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^{\...