Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms (1)

4
votes
2answers
409 views

Can powers of primes be perfect numbers?

I need to prove the following, though I'm not 100% certain I understand the definition of a perfect number. Prove that no perfect number is a power of a prime. First of all, I'm assuming that ...
6
votes
5answers
266 views

Show that $\gcd(a,b)=\operatorname{lcm}(a,b)$ if and only if $a=b$.

I know how to prove $a=b$ only if $\gcd(a,b)=\operatorname{lcm}(a,b)$, but I don't know how to prove the "if part". Can anyone help me?
1
vote
1answer
120 views

Does the continued fractions $3+\frac{1}{5+\frac{1}{7+\cdots}}$ equal $\pi$?

$3+\frac{1}{5+\frac{1}{7+\cdots}}=\pi$ Is it true? If yes, how to show it? Please help. Thank you.
0
votes
1answer
87 views

Induction, how often?

I have the following definition: $\quad p(x) \iff (x=0 \vee$ $\quad\quad\quad\quad\quad\quad\exists y\ (x=y+2\ \&\ p(y)) \vee$ $\quad\quad\quad\quad\quad\quad(x=1\ \&\ \forall y\ p(y*2)))$ ...
2
votes
5answers
658 views

Prove that $a^{(p-1)/2} \equiv 1$ (mod p) and $a^{(p-1)/2} \equiv -1$ (mod p)

I've stumbled upon this congruence very similar to Fermat's Little Theorem, but I can't seem to wrap my head around how to solve it. It goes like this: i) Suppose $p$ is prime, $(a,p)=1$ and the ...
2
votes
1answer
50 views

Prove $2x \equiv 1 \pmod m$, $x \equiv 1 \pmod n$ has a solution

I'm looking at the following problem: Suppose $m$ and $n$ are coprime, odd positive integers. Prove that the system of congruences $$2x \equiv 1 \pmod m\\ 4x \equiv 1 \pmod n$$ has a solution. I ...
3
votes
3answers
231 views

Prove that $12 \mid n^2 - 1$ if $\gcd(n,6)=1$

Prove that $12 \mid n^2 - 1$ if $\gcd(n,6)=1$. I know I have to use Fermat's Little Theorem for this but I am unsure how to do this problem.
2
votes
2answers
94 views

Number theory proof from AoPS

http://www.artofproblemsolving.com/Resources/articles.php?page=htw.readers In the above link, he gives a problem, namely Let $S(n)$ be the sum of the digits of $n$. Find ...
3
votes
2answers
203 views

Modular Multiplicative Inverse when multiplier greater than mod?

I'm having some trouble with this discrete math problem. I'm given this equation: $7x + 9y \equiv 0 \bmod 31$ and $2x -5y \equiv 2 \bmod 31$ And I've solved like I did my other one (which turned out ...
3
votes
1answer
43 views

Number Theoretic Problem

Let $n$ be a positive integer greater than $1$ such that $3n+1$ is a perfect square number. Then show that $n+1$ is the sum of three perfect square. I tried out the sum in different ways but cannot ...
1
vote
1answer
171 views

questions on Poulet numbers and Fermat pseudoprimes

I have found the following problems on Poulet numbers and Fermat Poulet numbers. I guess, I can have good explanation to complete my problems here. I want to prove or disprove the following: For ...
1
vote
1answer
28 views

Why is this map order-preserving?

Can somebody explain to me why $f: \mathbb N \rightarrow \{1,1+1,1+1+1,...\}$ where 1 is an identity element of ordered field, preserves order? Intuitivelly I understand that it does, but I don't ...
0
votes
2answers
122 views

Every equivalence relation on $\mathbb{Z}$ that is compatible with the addition structure is either the identity or the relation $\equiv \pmod{n}$

Let $R$ be an equivalence relation on $\mathbb{Z}$ such that the operation on the quotient set $\mathbb{Z}/R$ given by the rule $[x]_R + [y]_R = [x+y]_R$ is well-defined. Show that $R$ must either be ...
3
votes
0answers
132 views

Find specified sets of residues mod an even number

Let $k$ and $l$ be integers greater than $4$. I'm interested in set $S$ of $k$ elements in $\mathbb{Z}/2l\mathbb{Z}$ satisfying the following three conditions: (1) if $a\in S$, then $a+l\not\in S$; ...
0
votes
1answer
57 views

mod(d*e,n)=1, given e and n find d. Pen and paper method.

I have tried to run Euclid's algorithm in reverse to solve this problem but i'm not sure that it works. As above (in the title) the problem is to find mod($d \times e$,$n$)=1, given $e=7$ and $n=3120$ ...
0
votes
1answer
356 views

Given one number find a second number such that the gcd of both numbers is 1

I understand that the Euclidean Algorithm can be used as the pen and paper method to find the gcd of two numbers. However, I am studying the RSA algorithm and in this algorithm I need to find a number ...
28
votes
2answers
689 views

When is $2^n \pm 1$ a perfect power

Is there an easy way of showing that $2^n \pm 1$ is never a perfect power, except for $2^3 + 1 = 3^2 $? I know that Catalan's conjecture (or Mihăilescu's theorem) gives the result directly, but I'm ...
0
votes
2answers
77 views

Sieve of Erathosthenes - when can I stop crossing out?

Here is an exercise: Show that when finding the primes from 2 to $n$ using the Sieve of Erathosthenes, we can stop crossing out once $p \geq \frac{n}{2}$. Let $p$ be denoted by a star. Suppose ...
2
votes
1answer
718 views

Proof: Sequence of n consecutive natural numbers containing no primes (Velleman P158 Thm 3.7.3)

Theorem: For every positive integer $n$, there is a sequence of $n$ consecutive positive integers containing no primes. (Another MSE post about this Theorem) Proof: Since we desire "a sequence ...
1
vote
2answers
95 views

Problem: What is the remainder of $a^{72} \mod 35$ if $a$ is a whole number not having $5$ or $7$ as divisors.

I have the following problem: Problem: What is the remainder of $a^{72} \mod 35$ if $a$ is a whole number not having $5$ or $7$ as divisors. If $a$ cannot be divided by $5$ or $7$ it cannot be ...
2
votes
3answers
99 views

Problem: Decide positive whole number $e$ such that $13^e \equiv 32 (\mod 37)$

I have a problem: Decide positive whole number $e$ such that $13^e \equiv 32 \pmod{ 37}$ I know how to solve the equation $x^k \equiv b \pmod{m}$ where $k, b, m$ are given. However how do I find ...
6
votes
1answer
109 views

Number of elements in the resulting set of “subtraction game”

You have the following game: You start with a set $S$ with a number $n$ of positive integer elements, $n \ge 2$. At each step, you add to the set any new number $i$, as long as $i = |a-b|$ and $a$ ...
1
vote
0answers
108 views

Recommendation for a good book on equation solving theory from the basics

I'm relearning calculus but I often find myself applying algebraic operations to equations mechanically without having a solid understanding of the side-effects of those operations. Such as extra or ...
1
vote
3answers
104 views

Solve a congruence linear equation.

Solve the following congruence: $19x\equiv 1\;(\text{mod}\;36)$ My work: I found an inverse of $19$ and $36$ which is $9$. $9\cdot 19x\equiv 9\cdot 1\;(\text{mod}\;36)$ $171x\equiv ...
2
votes
1answer
98 views

Squares modulo a product of distinct odd primes

Let $p,q$ be distinct odd primes. Is it true that a number $a$ is a square modulo $pq$ if and only if $a$ is a square modulo $p$ and modulo $q$?
1
vote
4answers
142 views

If $\xi$ is irrational, $\xi+X$ is also irrational where X is rational number.

I am stuck while reading book FOUNDATIONS OF ANALYSIS by EDMUND LANDAU. I can't understand that how the number $\xi+X$ is always irrational whenever $\xi$ is irrational and $X$ is rational. The book ...
2
votes
2answers
32 views

Finding the exponent of a number which is a multiple of a large number

If $\frac{36^x}{3^{11}}$ is an integer, what is the smallest possible integer value of $x$? I'd like to know the approach to this problem.
2
votes
1answer
251 views

Need help with a zeta-like function?

Some time ago I found interesting modifications to Euler's prime product that produces a square number and its square root. The parts that were still unknown were the corresponding sums. I have ...
4
votes
2answers
189 views

Prove that there exists two integers $m, n$ such that $a^m + b^n \equiv 1 \mod{ab}$ with $(a,b) = 1$.

Prove that there exists two integers $m, n$ such that $a^m + b^n \equiv 1 \pmod{ab}$ with $(a,b) = 1$. Could you please give me some clues on how to solve this problem, not just show me the answer?
1
vote
2answers
711 views

Solving linear congruences with Fermat's theorem and Euler's theorem

Use Fermat's Theorem to solve $18X \equiv 23 \pmod{37}$ Use Euler's Theorem to solve $7X \equiv 39 \pmod{54}$ I don't see how these theorems would work in these instances
0
votes
1answer
54 views

If $g$ has order $n$, and $g^m=e$, then $n\mid m$

Let $G$ be a group and $g\in G$ an element of order $n$, i.e. $g^n=e$ but $g^p\neq e$ for any $0<p<n$. Show if $g^m=e$, then $n\mid m$. I want to use $m=qn+r$ with $0\leq r< n$.
3
votes
1answer
98 views

Primes Number Theory

For which primes $p$ is $2^p+1$ divisible by $p$? What I have been doing is: $2^p+1\equiv 0\pmod p$ $2^p\equiv -1\pmod p$ Then by Fermat's Theorem, we get $2^p\equiv 2\pmod p$ This shows ...
0
votes
1answer
229 views

For odd primes $p$, $n^{2p-1}\equiv n\pmod{2p}$

Prove or disprove: If $p$ is an odd prime, then $n^{2p-1}\equiv n\pmod{2p}$. I feel like there would be two cases, for when $n$ is odd and when $n$ is even but I'm not sure.
1
vote
1answer
96 views

Proof Checking and input: Generators of $\mathbb{Z}_{pq}$

I'm self-studying abstract algebra (slowly but surely), and I have a question about my answer to the following prompt: Problem statement: Show that there are $(q-1)(p-1)$ generators of the group ...
3
votes
1answer
387 views

Miller-Rabin primality test, begginer reading pseudo code

I was reading Miller-Rabin primality test Wiki and I can't understand something, it says that: Now, let $n$ be prime with $n > 2$. It follows that $n − 1$ is even and we can write it as $2s \cdot ...
0
votes
1answer
28 views

Asymptotic formula for $\# \{ n^{1/k} \in [N,2N] : n \in \mathbb{N}, \, k \in \mathbb{N}, k \leq K \}$

Fix $K \in \mathbb{N}$. Let $$ A_K(N) = \{ n^{1/k} \in [N,2N]: n \in \mathbb{N}, \, k \in \mathbb{N}, k \leq K \}. $$ What is the cardinality of $$ A_K(N) $$ for large $N$? Case $K = 2$: $$ \# ...
3
votes
2answers
71 views

Prove these are relatively prime. (involving Greatest Common Divisor)

I know that we have to use prime factorization. $\gcd(\alpha,\beta)$ => using minimum $\text{lcm}(\alpha,\beta)$ => using maximum $$\gcd(\alpha,\beta) \times \text{lcm}(\alpha,\beta) = a * b$$ ...
0
votes
3answers
77 views

Number theory question on primes and divisibility [duplicate]

For which primes $p$ is $2^p+1$ divisible by $p$? I am not quite sure how to approach this.
11
votes
1answer
224 views

Divisibility question from a very old textbook.

I have been looking at a rather old-fashioned book "The Tutorial Arithmetic" (1947), and have been amused by some of the questions in the "Harder Problems" section at the back of the book (some are ...
5
votes
1answer
139 views

371 = 0x173 (Decimal/hexidecimal palindromes?)

The decimal number 371 equals the hexadecimal number 0x173. The part that is relevant to me is that 371 is simply 173 backwards. Is this the only multiple digit decimal number that converts in this ...
4
votes
3answers
297 views

Is there any result, that says that $\lfloor e^{n} \rfloor$ is never a prime for $n>2$?

Is there any result, that says that $\lfloor e^{n} \rfloor$ is never a prime for $n > 2$ ?
4
votes
3answers
341 views

Number Theory Question - prove no integer solutions

Show that the equation $$x^2+xy-y^2=3$$ does not have integer solutions. I solved the equation for $x$: $x=\displaystyle \frac{-y\pm\sqrt{y^2+4(y^2+3)}}{2}$ $\displaystyle ...
1
vote
2answers
56 views

Number theory question [closed]

Let $r$ be the number of distinct prime factors of $m$. Show that there are exactly $2^r$ integers x such that $0\leq x<m$ and $x^2\equiv x\pmod m$
1
vote
0answers
100 views

Decryption of an Encrypted Message

Suppose we are given sending a message to two people: A and C. A and C have the same RSA encryption modulas: R=(some arbitrary number, say) 454564515456465465465156. But A and C have two different ...
3
votes
1answer
54 views

Last digit of a repeating period

In a collection of number theory problems, I found this one: Give the last digit of the decimal period of $$\frac{133}{7^{88}}$$ After we start simplfying to $$\frac{19}{7^{87}}$$ I don't know ...
1
vote
1answer
258 views

A man walks into a bank to cash a check for $d$ dollars and $c$ cents…

A man walks into a bank to cash a check for $d$ dollars and $c$ cents. The teller mistakenly gives him $c$ dollars and $d$ cents. He doesn't realize the error until he has spend 23 cents. At this ...
2
votes
1answer
144 views

If the mean of four non-negative integers a < b < c < d is 100, find the minimum value of a + d?

If the mean of four non-negative integers $a < b < c < d$ is $100$, what is the minimum value of $a + d$? It seems a easy problem..But I don't know how to solve it. Please help me.
1
vote
1answer
236 views

Prime and Factorization, prime divisor property

Let $p$ be prime. Then if $p|ab$ then $p|a$ or $p|b$. Proof: Suppose $p$ does not divide $a$ Then $\gcd (a,p) = 1$ since $p$ is prime. $$ 1 = ma + np $$ $$ b = mab +npb$$ Since $p|map$ and ...
2
votes
0answers
69 views

Prove that if $d_1=\gcd(a,b), d_2=\gcd(b,c), d_3=\gcd(c,a), D=\gcd(a,b,c)$, and $L=\operatorname{lcm}(a,b,c)$, then $L= \frac{abcD}{d_1 d_2 d_3}$

I tried to define: $a=d_1x_1$, $b=d_1y_1$; $b=d_2x_2$, $c=d_2y_2$; $c=d_3x_3$, $c=d_3y_3$. then $\operatorname{L.H.S} =d_1d_2d_3x_1x_2x_3=d_1d_2d_3y_1y_2y_3$ $\implies$ $x_1x_2x_3=y_1y_2y_3$; ...
6
votes
7answers
613 views

Prove $3|n(n+1)(n+2)$ by induction

I tried proving inductively but I didn't really go anywhere. So I tried: Let $3|n(n+1)(n+2)$. Then $3|n^3 + 3n^2 + 2n \Longrightarrow 3|(n(n(n+3)) + 2)$ But then?