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

learn more… | top users | synonyms (1)

1
vote
1answer
52 views

Proof verification: Proving that $\gcd(p,q,r)>1$

If gcd(p,q,r) = 1 Prove that there is an integer A such that gcd(p, q+Ar) = 1 Is the following proof good (correct)? If we assume for the sake of contradiction that $\gcd(p,q+Ar)$ $>1\ \forall A\...
1
vote
5answers
73 views

Let $n$ be a three digit number. Prove or give a counter example: $9|n$ if and only if the digits of $n$ sum to a multiple of $9$.

Let $n$ be a three digit number. Prove or give a counter example: $9|n$ if and only if the digits of $n$ sum to a multiple of $9$. I was able to go from left to right. But I'm having a hard time ...
0
votes
2answers
63 views

if $n$ is a Prime number and $\omega \neq 1$ then $1+\omega+\omega^2+…+\omega^{n-1}=0$

Let $n$ is a Prime number , $\omega \neq 1$ is a n-th root of unity , show that Other to form the n-th roots are $\omega ,\omega^2,...,\omega^{n-1}$ and we have $1+\omega+\omega^2+...+\omega^{n-1}=0$
2
votes
0answers
52 views

Conceptual question on showing properties of the absolute value function on $\mathbb{Q}$

I have a rather conceptual question about showing certain small lemmas regarding the absolute value function on $\mathbb{Q}$. I want to only give one example: Let $a,b \in \mathbb{Q}$ and $|.|$ ...
2
votes
0answers
25 views

If $\gcd(p,q+Ar)>1$ for all $A\in \mathbb{Z}$, then $\gcd(p,q,r)>1$ [duplicate]

Prove that if $\gcd(p,q+Ar)>1$ for all integers $A$, then $\gcd(p,q,r)>1$. I let $A=0$ to get that $\gcd(p,q)>1$. Then I noticed that $\gcd(p,q,r)=\gcd(\gcd(p,q),r)$. Another way to say it: ...
5
votes
1answer
96 views

An interesting problem with natural numbers

While, preparing for competition, found an interesting problem, but absolutely don't know how to start. $600$ natural numbers from $1$ to $600$ are written in a string(each once) in a certain order, ...
7
votes
4answers
420 views

Three baskets and transferring apples

This is from a math contest, and I do not have the idea how to approach it: There are 6, 7, and 11 apples in three baskets. The goal is to make all basket contain equal number of apples, but ...
6
votes
2answers
611 views

How are the elementary arithmetics defined?

In the book Principles of Mathematical Analysis by Rudin, I read that "a < b" is defined this way: if b - a is positive, then a < b or b > a. Then some questions arose to me: we know that "minus"...
2
votes
1answer
38 views

If $a^{8}+a^{7}-a^{5}-a^{4}-a^{3}+a+1= mn$ then $m\equiv n\equiv 1 \pmod{15}$

How to prove: in integers for any $a$ If $$a^{8}+a^{7}-a^{5}-a^{4}-a^{3}+a+1= mn,$$ then $$m\equiv n\equiv 1 \pmod{15}.$$ ?
0
votes
6answers
4k views

Why is two the only even number that is prime?

The other prime numbers are all odd numbers such as $5, 11, 127,$ and $37$. So, why is $2$ the only prime even number there is? Maybe it's because it only has 1 and itself that way, even though it's ...
0
votes
3answers
3k views

Why is one the only positive number that is neither prime nor composite?

I've heard stories about why the number $1$ is neither a prime number nor a composite number, even on in the middle of this awesome math page. Just scroll down to the middle to read about it. It's a ...
1
vote
4answers
44 views

How to prove that the set of all not-empty and finite subsets of $\mathbb{N}$ is countable? [duplicate]

The set of all subsets of $\mathbb N$ is $ \mathcal{P}{(\mathbb N)} $ right? So how can I prove that $ \mathcal{P}{(\mathbb N)} $ is countable?
1
vote
2answers
85 views

Why is a union of n countable sets countable? [duplicate]

I have to show that $$ \bigcup_{n=1}^{\infty}A_{n} := (a: \exists n \in \mathbb{N}: a \in A_{n}) $$ EDIT: So beneath this edit were just my thoughts. Above is the task. Is there any elementary way ...
2
votes
2answers
46 views

How do I show that a mapping is bijective?

How do I show that $$ g: \mathbb{N} \times \mathbb{N} \to \mathbb{N}, (m,n) \to 2^{m-1}(2n-1)$$ is bijective? Any tips or help for me? I'm kind of stuck. EDIT: I know what bijective means but my ...
4
votes
4answers
476 views

Prove whether this number is or is not prime [closed]

Is the number 2438100000001 composite or prime? Please first give a hint if you already know the answer.thanks!
1
vote
0answers
29 views

Why do we conclude that $(a,b)=1$, having found that $(a',b'=1)$?

Suppose that we have the equation $ax^2+by^2+cz^2=0, a,b,c \in \mathbb{Q}$. Without loss of generality, we suppose that $gcd(a,b,c)=1$. Also, we can consider that $a,b,c$ are square-free. We can ...
2
votes
3answers
458 views

Infinite primes of the form 3n+2

Without recourse to Dirichlet's theorem, of course. We're going to go over the problems in class but I'd prefer to know the answer today. Let $S = \{3n+2 \in \mathbb P: n \in \mathbb N_{\ge 1}\}$ ...
0
votes
1answer
78 views

Number theory : properties of the first prime numbers 2,3,5,7

Let $p,q,r$ and $s$ be four distinct prime numbers chosen among the set $\{2,3,5,7\}$ and we look for all the $4$-tuples of integers > 0 $(a,b,c,d)$ such that: $$p^a = q^b + (r^c)\cdot(s^d)$$ There ...
5
votes
1answer
93 views

Does the A001921 linear recurrent integer sequence always yield composite numbers?

Let $(a_n)$ be the A001921 sequence $$ a_0 := 0,\ a_1 := 7, \quad a_{n+2} = 14a_{n+1} - a_n + 6. $$ Is it true that $a_n$ is always a composite integer for any $n\geq 2$ ? UPDATE : I now make a ...
2
votes
1answer
117 views

Prime representable as $ x^2 + 3y^2 $

I'm to prove that if $ p = 3k+1 $ is a prime greater than $ 3 $ then there exist $ x,y \in \mathbb{Z} $ such that $$ p=x^2 + 3y^2.$$ I just don't know how to begin. All I have is Thue lemma and it ...
0
votes
1answer
30 views

Representation of a prime

I'm having trouble with proving the following implication: Prove that if (-4) is a square $ \pmod{p} $, then $ p $ is representable as $ x^2 + 4y^2 $ in $\mathbb{Z}$. So I was thinking that maybe ...
0
votes
1answer
90 views

Using the ABC-conjecture

I have to answer the following question: Let $a,b,c \in \mathrm{Z}_{\geq3}$, use the ABC conjecture to show (we suppose that the conjecture is true) that $x^ay^b-z^c=1$ has finite solutions for $x,y,...
70
votes
6answers
8k views

Do we have negative prime numbers?

Do we have negative prime numbers? $..., -7, -5, -3, -2, ...$
-1
votes
1answer
70 views

About the sigma function and an interesting inequality. [closed]

Is it true $\sigma(A)$/$\sigma(B)$ > = (A/B) ; given B divides A ?
0
votes
1answer
37 views

Find the number of integers n such that the equation

Find the number of integers n such that the equation $xy^2+y^2-x-y=n$ has an infinite number of integer solutions $(x,y)$.
3
votes
1answer
100 views

How many duplication formulas exist for the Mordell curve family $Y^2-X^3=c$?

For the Mordell equation $$ Y^2-X^3 = c, $$ Bachet gave a famous duplication formula which translates one rational solution $(x_1,y_1)$ into a second rational solution $(x_2,y_2)$. Réalis gave a ...
1
vote
2answers
217 views

Does the equation has a non-trivial solution?

Could you give me some hints how I can solve the following exercise? Check if the equation $3x^2+7y^2-5z^2=0$ has a non-trivial solution in $\mathbb{Q}$ . If it has a solution, find at least one. If ...
0
votes
2answers
89 views

find a parametric solutions for a special equation

Let $a,b,c$ be rational.Find a rational parametric solutions for $a,b$ and $c$ so that simultaneously $$a^2-c^2=\square$$ and $$b^2-c^2=\square$$
3
votes
3answers
127 views

Proof that an odd integer multiplied by 3 and squared is always odd

I'm working with a proof in a discrete structures CS course, and I am a little confused by how to build up some logic for the argument. Currently we're working with symbolic logic, the problem ...
7
votes
2answers
99 views

$ab$ divides $3^a+1$ and $3^b+1$

Find all positive integers $a,b$ such that $ab$ divides $3^a+1$ and $3^b+1$. It is clear that $3$ cannot divide either $a$ or $b$, because $3$ doesn't divide $3^a+1$ or $3^b+1$. $(a,b)=(1,1),(2,1),(...
1
vote
1answer
53 views

Find sufficient and necessary conditions in which $(6m+2)/n$ is not a natural number

Let $m$ and $n>1$ two integers. Find sufficient and necessary conditions in which $\frac{6m+2}{n}$ is not a natural number.
1
vote
2answers
86 views

Uniqueness of Extended Euclidean Algorithm

I'm doing a bit of extra reading on the Extended Euclidean Algorithm and had a side-thought that I couldn't find an answer to in the book. I understand that the Extended Euclidean Algorithm can ...
11
votes
1answer
194 views

Proving that $(3n)!$ is divisible by $n! \times (n + 1)! \times (n + 2)!$ if $n$ is greater than 2

Prove that: If $n$ is greater than 2, then $(3n)!$ is divisible by $n! \times (n + 1)! \times (n + 2)!$ From Barnard & Child's "Higher Algebra". I know that the highest power of a prime $p$ ...
0
votes
1answer
23 views

Sets with no Prime Number-Generating Subsets

Are there arbitrarily large sets $S \subset \mathbb N$ such that the set $\{1\} \cup S$ has no subset that sums to a prime number?
5
votes
2answers
83 views

Function with $f(a)-f(b)$ dividing $a^3-b^3$

What are all functions $f:\mathbb{Z}\rightarrow\mathbb{Z}$ such that $f(a)-f(b)$ divides $a^3-b^3$ for all $a,b\in\mathbb{Z}$ such that $f(a)\neq f(b)$? The constant functions satisfy vacuously, and ...
1
vote
6answers
2k views

Why are there letters as additional digits in bases greater than the decimal base (10)?

For example, in the hexadecimal base (16), the letters A through F are included as digits, but why? This letter thing happens in bases greater than ten. For example, in the hexadecimal base, C is 12 ...
5
votes
1answer
91 views

Maximum number dividing $\prod_{i<j}(a_i-a_j)$

Fix an integer $n$. What is the maximum number guaranteed to divide $\prod_{i<j}(a_i-a_j)$ for any integers $a_1,\ldots,a_n$? For instance, if $n=3$, then two of the three numbers have the same ...
0
votes
1answer
69 views

Find all $m,n$ such that $mn|n^2+m^2+1$

$n$ and $m$ are positive integers. Find all values of division from $\dfrac{n^2+m^2+1}{nm}$ if $n^2+m^2+1$ is divisible by $nm$. Every suggestion is desired. Thanks.
0
votes
2answers
89 views

Congruence Proof Involving Fermat's Little Theorem

Let $n \in\mathbb N$. Use Fermat’s little Theorem to show that if a prime $p$ divides $n^2 + 1$, then $n^{p−1} \equiv 1 \pmod p$. So far, I have written that I need to show $n^2 \equiv -1 \pmod p$. ...
13
votes
1answer
315 views

Combinatorial prime problem

Update As Barry Cipra noted in the comments, a better framing of the question might be that I'm looking at absolute differences $|a−b|$ or totals $a+b$ for $5$-smooth numbers $a$ and $b$ satisfying ...
7
votes
0answers
78 views

Integers neither as sum nor difference of perfect powers

Are there infinitely many positive integers $n$ for which there do not exist integers $a,b\geq 1$ and $c,d\geq 2$ such that $n=a^c+b^d$ or $n=a^c-b^d$? [Source: Hungarian competition problem]
1
vote
4answers
211 views

Help proving $9^n-8n-1$ is divisible by $8$ for all $n > 1$ by induction

I have been trying to prove that $9^n-8n-1$ is divisible by $8$ for all $n$ integers greater than 1. My progress: Let $n = 2$. This gives us the expression equal to $64$ which is a factor of 8. Now ...
0
votes
1answer
75 views

Combinatorial prime puzzle

Is it true that no prime larger than $241$ can be made by either acting or subtracting $2$ coprime numbers made up out of the prime factors $2,3,$ and $5?$ Update Above example is clearly wrong, as ...
0
votes
2answers
63 views

Let $a, b, c$ be positive integers such that $\gcd(a,b,c) = 1$ and $a^2+b^2=c^2$. Prove that $12$ divides $abc$.

I already have the equations: $a = xy, b = \frac{x^2-y^2}{2}, c = \frac{x^2+y^2}{2}$ with $x > y \geq 1$
3
votes
2answers
50 views

If $\gcd(7,abc)=1$ and $a^2+b^2=c^2$, prove that $7$ divides $a^2-b^2$

The only information I have on this problem is that for $a^2+b^2=c^2$ that $$ a = st, b = \frac{s^2-t^2}{2}, c = \frac{s^2+t^2}{2} $$ and that $\gcd(7,abc)=1$ gives $7x + abcy = 1$ I have no idea how ...
3
votes
2answers
75 views

Integer solutions of the equation $7(a^2+b^2)=(c^2+d^2)$

What are all the integer solutions of the equation $7(a^2+b^2)=(c^2+d^2)$ First thing to note is that $c=7C$ and $d=7D$ and substituting it in the original equation yields an equation that is ...
1
vote
1answer
38 views

Show that $\sinh^2[2^{j-1}\cosh^{-1}( 2)]+1$ is still a natural number for all natural numbers $j$

Show that this real number $$\sinh^2[2^{j-1}\cosh^{-1}( 2)]+1$$ is still a natural number for all natural numbers $j$.
13
votes
3answers
2k views

Very elementary proof of that Euler's totient function is multiplicative

Well, I know two or three proofs of this fact $$\gcd(m,n)=1\implies \varphi(mn)=\varphi(m)\varphi(n)$$ where $\varphi$ is the totient function. My problem is this: I'd like to explain this to some ...
1
vote
1answer
69 views

Primality Test for Safe Primes

Is this proof acceptable ? Theorem Let $N$ be of the form $N=2p +1$ with $p$ prime , then $N$ is prime iff $N \mid 2^{2p}-1$ Proof In one direction , if $2p+1$ is a prime then by Fermat ...