2
votes
0answers
22 views

A primitive root exists modulo $n$ if and only if $n=2$, $n=4$, $n=p^k$, or $n=2p^k$ with $p$ an odd prime.

I have already proven that primitive roots exist modulo $p^k$ and $2p^k$ for an odd prime $p$. I'm having trouble proving the other direction. Is it simply due to the fact that if $p,q$ are distinct ...
0
votes
0answers
6 views

how to sum the divisors of N mod K if all I have is N mod K?

The input to this problem is N. I have to calculate 2 things: 1 - N! mod (10^9 + 7) 2 - sum of all divisors of N! mod (10^9 + 7) I know how to do the first step, I'm wondering if there is a way ...
0
votes
1answer
30 views

If $a\pmod 3 \equiv 1$ and $b\pmod 3 \equiv 2$, then $ab \pmod 3 \equiv 2$

I'm stuck on this this problem: Let $a$ and $b$ be positive integers with $a\pmod 3 \equiv 1$ and $b\pmod 3 \equiv 2$. Prove that $ab \pmod 3 \equiv 2$. I think the first step for the direct ...
2
votes
1answer
26 views

Equivalence classes modulo 7 are pairwise disjoint

Where do I got from here? I really really have no idea.
1
vote
1answer
26 views

Find the remainder of $(p-2)!$ module $p$, where $p$ is a prime $\geq 3$

My attempt: From Wilson's Theorem: For a prime $p$, $$(p-1)! \equiv (-1) \pmod p$$ Multiplying both sides by $(p-2)$, $$(p-2)! \equiv -(p-2) \pmod p$$ i.e. $$(p-2)! \equiv 2 \pmod p$$ So the ...
1
vote
5answers
1k views

Prove that the sum of three consecutive squares, minus two is a multiple of 3

Prove that if you add the squares of three consecutive integer numbers and then subtract two, you always get a multiple of 3.
0
votes
7answers
60 views

Show that if a positive integer $ n $ is composite then $ R(n) = \frac{10^{n}-1}{9}= 111…11 (n times) $ is composite [duplicate]

Show that if a positive integer $ n $ is composite then $ R(n) = \frac{10^{n}-1}{9}= \underset{n\text{ times}}{\underbrace{111...11}} $ is composite I attempted a both a normal proof and proof by ...
3
votes
5answers
89 views

How to select the right modulus to prove that there do not exist integers $a$ and $b$ such that $a^2+b^2=1234567$?

I understand the solution but I don't know how the author decided to start with modulo 4 instead of something else? What is it about the expression $a^2+b2=1234567$ that would trigger us to select ...
1
vote
4answers
71 views

Can anyone explain how to show that $n^{5} -n ≡0$ mod $30$ for every $ n \in \mathbb{N} $

I first tried to answer this using proof by induction, however my problem got more complicated when I got to the induction step. Is there another way of solving this problem?
0
votes
3answers
33 views

Proving the GCD

Let $a= 16673011647$. Let $b = 16213295811$. Using the fact that $a \times −77566962 + b \times 79766315 = 51$, prove that $51$ is the gcd of $a$ and $b$. The part that is confusing is, using the ...
5
votes
5answers
315 views

polynomial with positive integer coefficients divisible by 24?

I have to show that $n^4+ 6n^3 + 11n^2+6n$ is divisible by 24 for every natural number, n, so I decided to show that this polynomial is divisible by 8 and 3, but I'm having trouble showing that it is ...
0
votes
2answers
66 views

Day of the week from the date.

I still remember when I was a kid some senior student used to ask us a date from history and then tell us what day was then within 20 seconds. I read montgomery's Number theory and when found the ...
-2
votes
1answer
34 views

Question on the relationship of a quantity and its value modulo n [closed]

Is it correct to say that if there are 13 chameleons, then there are $1\pmod 3$ chameleons? If so, why?
0
votes
1answer
41 views

Fast modular exponentiation

Suppose that $p$ and $q$ are distinct primes, then for every integer $a$ and exponent $e$ with $e\not \equiv (\bmod \,(p - 1)(q - 1))$ show that: ${a^e} \equiv {a^{e\, \cdot \,\bmod \,(p - 1)(q - ...
3
votes
3answers
62 views

Prove the following fraction is irreducible

Prove $\frac{21n + 4}{14n + 3}$ is irreducible for every natural number $n$. I was thinking of taking a number-theory based approach. Can you suggest the following method Calculus/Number theory ...
0
votes
2answers
58 views

Find integers x and y with 103x + 113y=1

Find integers $x$ and $y$ with $103x + 113y=1$ How would you solve this problem? I'm thinking maybe you can use Euclidean Algorithm to solve for the inverse?
2
votes
1answer
89 views

The number $2^{29}$ has $9$ distinct digits. Find the missing digit without the use of a calculator. [duplicate]

$2^{29}$ has $9$ distinct digits. Find the missing digit without the use of a calculator. I've seen its solution before but I still don't understand it. Math novice here. A detailed answer will ...
1
vote
2answers
29 views

Proof of Little Fermat's Theorem for a=7

In the book I read there are proofs of FLT for certain cases before the common case. When a=7, authors first write that it's possible to check all remainders of $a\mod7$, and then that it's ...
1
vote
3answers
55 views

Simplifying a proof by contradiction: if $a\equiv 1\bmod 5$, then $a^2\equiv 1\bmod5$

Prove the following either by Direct Proof or by Contraposition: Suppose $a\in\mathbb{Z}$, if $a\equiv 1\pmod 5$, then $a^2\equiv 1\pmod5$ Suppose $a\equiv 1\pmod 5$ Then $5|\left(a-1\right)$, ...
2
votes
1answer
34 views

The modular n-th root (mod p*q)

I am interested in the solution of the following modular equation. Is the solution unique? If not, how difficult do find more than one solutions? $$x^n \equiv a \; \bmod (p\cdot q)$$ where $p$ and ...
0
votes
3answers
46 views

Congruences in number theory

I am working on a worksheet on number theory and I have to solve the following congruences: $$7^{128}=n\mod 13$$ Find $n$. And $$28x^2=1\mod37$$ How should I solve these congruences? I have no clue ...
1
vote
2answers
72 views

Find the remainder when $2^{561}$ is divided by $561$ using simple congruence properties.

$2^{561}\equiv ? \pmod{561}$ Few observations : $561 = 3\times 11\times 17$ So Fermat's little theorem is not useful here. Any hints ? If possible, kindly avoid carmichael numbers/group theory/euler ...
0
votes
0answers
21 views

Modular nth roots, e.g. $x^5 \equiv 6 \pmod{31}$

I want to algorithmically solve the (large integer) modular root equation $$x^n \equiv a \pmod {p^k},$$ assuming for simplicity that $p$ is prime, $\gcd(a,p)=1\;$ and $n$ odd. If $q \equiv n^{-1} ...
0
votes
0answers
31 views

How can I solve equations involving modulo both side like this one?

I need to find $x \bmod m$ from the below equation: $$((p \bmod m)(x \bmod m)) \bmod m \equiv q\bmod m$$
3
votes
1answer
35 views

Find the order of $2$ in $\mod 2^{n} -1 $

Find the order of $2$ in $\mod 2^n-1$ I know that the order of $2$ in $\mod 2^n-1$ is the smallest positive integer $k$ such that $$2^k \equiv 1 \pmod {2^n-1}$$ How to proceed from here ? Any ...
2
votes
2answers
36 views

Does $x\equiv ay \pmod{p^{2m}}$ always have non-trivial solutions $x,y$ with $\lvert x \rvert,\lvert y \rvert \leq p^m$?

Given a positive integer $m$, a prime $p$ and an integer $a$, I would like to prove that $$ x \equiv ay \pmod{p^{2m}} \qquad \lvert x \rvert,\lvert y \rvert \leq p^m $$ always has at least one ...
2
votes
2answers
71 views

What is the remainder when $12^{39} + 14^{39}$ is divided by $676$?

I tried following but then I got stuck $676 = 26*26$ $12^{39} + 14^{39}$ is divisible $26$ for sure since $a^n + b^n$ is divisible by $(a+b)$ when $n$ is odd. But what to do next?
2
votes
2answers
74 views

general form in congruence

Could we generalize this example of congruence issue for $x,n \in \mathbb{Z}_*$? $$ 1+x+\cdots + x^{n-1}\equiv n \pmod {x-1} $$
2
votes
2answers
107 views

congruence issue

I need to understand why this : $$(1+4+\ldots+4^{n−1})\equiv n \pmod3$$ Is that because \begin{align} 1&\equiv -2 \pmod3\\ 4&\equiv 1 \pmod3\\ 4^{2}&\equiv1 \pmod3\\ ...
0
votes
1answer
46 views

Proof of Floyd Cycle Chasing (Tortoise and Hare)

I am looking for a proof of Floyd's cycle chasing algorithm, also referred to as tortoise and hare algorithm. After researching a bit, I found that the proof involves modular arithmetic (which is ...
1
vote
3answers
80 views

The final digit of fourth powers

I am working on "Elementary Number Theory" By Underwood Dudley and this is problem 13 in Section 4. The question is "What can the last digit of a fourth power be?" I got the correct answer but I'm ...
3
votes
0answers
48 views

Combinatorial interpretation of an equality

In a recent project, I came up with the following equality which turned out to be extremely useful for counting conjugacy classes in certain division algebras (I won't go into the details here, it's ...
3
votes
2answers
86 views

Finding $23! 7! \bmod 29$ using Wilson's Theorem

I'm trying to reduce $23!\,7! \bmod 29$. I used Wilson's Theorem to get $23!(120)\equiv 1 \pmod{29}$. I then solved $120a\equiv 1 \pmod{29}$ and got $a\equiv 22$. I then computed $7! \pmod {29}$. ...
7
votes
3answers
131 views

How to prove that $53^{103}+ 103^{53}$ is divisible by 39?

This is a problem in my number theory textbook. It is based on modular arithmetic but im not getting how to start off to prove this. Please give me some hints on how to solve it.
1
vote
2answers
45 views

Proof that the congruence relation on $\mathbb Z$ is transitive (attempt shown)

I have answered this question to the best of my knowledge but somehow I feel as if I am missing something? Can I further prove this statement or add anything to it? Question: Let $m \in \mathbb ...
3
votes
3answers
89 views

Raising $2$ to the power of $2014^ {2013}$ modulo $41$

The question is as follows: $$2^{{2014}^{2013}}$$ Determine its remainder by division with $41$. I know that I need to use $\bmod 41$ and reduce the power somehow to something that can be solved ...
1
vote
1answer
62 views

Find $n$ between $100$ and $1000$ so that $2^n+2$ is divisible by $n$

Find $n$ such that $n$ divides $2^n + 2$. Also, $n$ should be between $100$ and $1000$. It can be easily seen that $n$ is not a multiple of $4$. By brute force I have figured out that answer is ...
1
vote
1answer
49 views

Residue class of a huge repunit modulus a huge number

Given a number with only 1: X = 1111...1 (N times 1 in total), and another number M, I want ...
0
votes
1answer
89 views

How to find out a^b^c^… mod m

I would like to calculate: abcd... mod m I know when a is coprime to m then we can easily find out the answer using Euler's totient function. But I wish to know the ideas when a is not coprime to ...
1
vote
1answer
41 views

Find modular inverse of a number

Recently I have read extended euclid's algorithm which is used to find out the modular inverse of a number N whith respect to MOD such that $\gcd(N,MOD)=1.$ But I have a doubt that how to find modular ...
4
votes
0answers
194 views

Prove modular equivalence related to carmichael function.

Statement if $n=p_1p_2p_3\cdots p_r$ (prime numbers are distinct) and $2 \le a \le n-1$ then prove that $$a^{k\lambda} \equiv \left(1+\sum_{p_i\mid\gcd(a,n)}\left(\dfrac{n}{p_i} \right) ...
3
votes
4answers
104 views

Remainder when $11^{2402}$ is divided by $3000$? [closed]

What is the remainder when $11^{2402}$ is divided by $3000$? I just came across this question. I am a beginner in number theory. Your help would mean a lot.Thanks!!
1
vote
3answers
90 views

How to solve this modular equation? $x^{19} \equiv 36 \mod 97$.

How to solve the following? $x^{19} \equiv 36 \mod 97$. I am having trouble figuring this out. Which technique do I need to use? Chinese Remainder or Fermat's Little Theorem?
1
vote
0answers
24 views

In $Z[x]$, which pairs of $a,b$ commute as modulo operators, such that ($c$ mod $a$) mod $b =$ ($c$ mod $b$) mod $a$ for every $c$?

In $Z[x]$, which pairs of $a,b$ commute as modulo operators, such that ($c$ mod $a$) mod $b =$ ($c$ mod $b$) mod $a$ for every $c$? What I got so far is: Clearly the equasion holds for every pair ...
4
votes
2answers
97 views

Binomial Congruence Modulo a Prime

Let $p$ be a prime and $a, b$ natural numbers such that $1 \leq b \leq a$. I am trying to prove that $$\binom{ap}{bp} \equiv \binom{a}{b} \pmod p.$$ Furthermore, I have been tasked with proving that a ...
1
vote
5answers
89 views

finding mod of an expression with variables

I've been asked to show that: $n(n+1)(2n+1) \equiv 0 (\bmod 6)$ I found in a previous question that: $n(n+1)$ was divisible by $2$ and resulted in an even number e.g $n(n+1) \equiv 0 (\mod 2)$ so ...
0
votes
1answer
28 views

Converting infinite base-k expansions into base-j expansions

I understood the method of transforming a finite sized base-k numbers to another base (j) through the use of successive divisions For example $$12_{10} = 12/2 + 0*2^0 = 6/2 + 0*2^1 + 0*2^0 = 3/2 + ...
0
votes
0answers
41 views

What is the remainder of this big number without doing major calculations?

I am solving a problem and came across a situation where to calculate remainder for big values with out doing major calculation. In my case I need to compute the expression: $$2^{n}-1+k ...
2
votes
5answers
89 views

What is remainder when $5^6 - 3^6$ is divided by $2^3$ (method)

I want to know the method through which I can determine the answers of questions like above mentioned one. PS : The numbers are just for example. There may be the same question for BIG numbers. ...
0
votes
3answers
74 views

Prove that $n^2 + 1$ is not a multiple of $6$ for any positive integer $n$

Prove that $n^2+1$ is not a multiple of $6$ for any positive integer $n$. I i think prime factorization would be a good way to go about this problem but I need some help.