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

learn more… | top users | synonyms (1)

0
votes
1answer
28 views

Form of Divisors of Proth numbers

Proth number is a number of the form : $z⋅2^k+1$ where z is an odd positive integer and k is a positive integer such that : $2^k>z$ Is there a form for divisors of Proth Numbers? (Like Mersenne ...
11
votes
6answers
6k views

Find two numbers whose sum is 20 and LCM is 24

With some guess work I found the answers to be 8 and 12. But is there any general formula for this? Note that the question is asked to my nephew who is at 4th grade.
2
votes
1answer
63 views

Existence of two primes satisfying the given conditions

I want to know whether the equation $x^a-x=y^b-y$ has a solution or not satisfying the conditions that $x$ and $y$ are distinct odd primes, $a$ and $b$ are integers both greater than $1$.
1
vote
1answer
668 views

$n,a,b \mathbb \in \mathbb Z^+$ , such that $n\mid a^n-b^n$ ; to show $n\mid \frac {a^n-b^n}{a-b}$ [duplicate]

Let $n,a,b \in \mathbb Z^+$ be such that $n\mid a^n-b^n$ , then how to prove that $n\mid {\dfrac {a^n-b^n}{a-b}}$ ? My try : $d=\gcd(n,a-b),$ so $d \mid{\dfrac {a^n-b^n}{a-b}}.$ Also $\,n \mid(a-...
2
votes
3answers
69 views

Number Theory Simple Proof Confusion

Suppose that c|ab and (b, c) = 1. Then c|a Proof (ab, ac) =|a|(b, c) = |a|. But by hypothesis, one has c|ab, which implies that c|(ab, ac). We thus conclude that c|a. And the proof is complete. I am ...
5
votes
1answer
122 views

Find a positive integer $n$ such that $ϕ(n) = ϕ(n + 1) = ϕ(n + 2)$

I need to find a positive integer $n$ such that $ϕ(n) = ϕ(n + 1) = ϕ(n + 2)$ where $ϕ(n)$ denotes Euler's totient function. What I am given: (1) You may take $ϕ(n) = 2592$. (2) $ϕ(2n) = ϕ(n)$ ...
5
votes
2answers
155 views

Prove $n^2+4n+3$ is not prime for $n \in \mathbb{Z}^{+}$.

I am trying to write a proof for this theorem: For every positive integer $n$, $n^2+4n+3$ is not a prime. Proof: Let $n \in \mathbb{Z}^{+}$. Note that $$n^2+4n+3=(n+1)(n+3)>1\text{,}$$ and $...
1
vote
1answer
43 views

If $p \equiv 1 \pmod{N!}$ prove there are no primitive roots $\pmod p$, $g$, that are less than $N$ [duplicate]

I've recently been looking at different questions and proofs in my book and one eludes me for the 2nd day in the row. Let $N \geq 4$. Show that if $p$ is a prime such that $p \equiv 1 \pmod{N!}$ ...
4
votes
2answers
174 views

What are all the twin primes $p$ and $q = p + 2$ for which $pq - 2$ is also prime?

It seems that $p = 3$ and $q = 5$ ($pq - 2 = 13$) are the only solutions. However I'm having a difficult time proving this. I have that all primes can be represented as $3k + 1$ or $3k + 2$ so if $p ...
10
votes
2answers
810 views

Why does this cube root trick work?

So, I found that you can work out cube roots between $1$ and $100$ using this method: For example the number: $185193$ If the last digit $x$ is $2$, $8$, $3$, or $7$, the last digit in the answer ...
-1
votes
1answer
162 views

Proving that for each $n \in \mathbb{N}$ there is an $m \in \mathbb{N}$ such that $m > n$ from certain axioms

I am trying to prove the following proposition: For each $n \in\mathbb N$ there exists $m \in\mathbb N$ such that m > n. Here are my axioms: If $m,n \in\mathbb N$ then $m + n \in\mathbb N$ If ...
0
votes
5answers
86 views

Prove that $3n6n3^2+4n8n4^2$ yields a perfect square.

Let $n\geq 0$ be a nonnegative integer. I observed that the expression $3n6n3^2+4n8n4^2$ is always a perfect square where $n$ represents number of "0". And I had verified it by using a calculator ...
1
vote
1answer
25 views

Let $m = 2^ap_1^{b_1}p_2^{b_2}…p_r^{b_r}$ where $a\geq 0,r \geq 0, b_i \geq 1$.

How many incongruent solutions are there to $x^2 \equiv 1 \space (mod \space m)$? As a hint, my teacher said make use of the Chinese Remainder Theorem. What I have done so far is a case by case ...
0
votes
1answer
37 views

Question about negative Pell's Equation

Is it true that, if $a^2-Db^2=-1$ is solvable in integers, then so is $x^2-Dy^2=D$ (*)? For $D=5$ this is true, you can take $x=5$ and $y=2$, and indeed $5^2-5(2^2)=5$, so (*) is solvable. Is this ...
2
votes
0answers
70 views

Using the pigeonhole principle to prove there is at least a sum of numbers bigger than 29.

There is a circumference with 14 points $\{p_{1}, p_{2}, ... p_{14}\}$. These points are assigned numbers 1 to 14 randomly. It must be proven that if points are taken three-by-three, these triplets ...
1
vote
1answer
67 views

Question about Negative Pell Equations

Does every soluble negative pell equation, $a^2-Db^2=-1$, have infinitely many integer solutions $(a,b)$ where $a,b$ are both positive integers?
3
votes
1answer
91 views

Pell Equations: $a^2+4=5b^2$

This is a challenge problem in the Pell Equations chapter of my number theory book, but I'm not seeing the connection to Pell Equations. The Pell Equation with the coefficient $5$ is $5b^2+1=a^2$, but ...
6
votes
3answers
234 views

Linear Diophantine Equations in Three Variables

$$ 3x+6y+5z=7 $$ The general solution to this linear Diophantine equation is as described here (Page 7-8) is: $$ x = 5k+2l+14 $$ $$ y = -l $$ $$ z = -7-k $$ $$ k,l \in \mathbb{Z} $$ If I plug the ...
7
votes
3answers
229 views

When is $2^x+3^y$ a perfect square?

If $x$ and $y$ are positive integers, then when is $2^x+3^y$ a perfect square? I tried this question a lot but failed. I tried dividing cases into when $x,y$ are even/odd, but still have no idea ...
3
votes
3answers
3k views

Number of six-digit integers with increasing digits [duplicate]

How many six-digit positive integers can you write, if each number must have strictly increasing digits from left to right? How is it allowed to use: $$ \binom{9}{3}$$ Because this says out of $9$ ...
0
votes
2answers
23 views

To show $m \mid \sum_{i \in (\frac{\mathbb{Z}}{m \mathbb{Z}})^*} i$

Let $m\geq 3$, I need to show that $ d \equiv 0 \ mod \ m $ where $d=\sum_{i \in (\frac{\mathbb{Z}}{m\mathbb{Z}})^*} i$ . That is if we sum all elements in the group of units in $\frac{\mathbb{Z}}{m\...
1
vote
1answer
39 views

Pick's Theorem for plane triangles in $\mathbb{R}^{3}$?

Pick's theorem asserts that, given a simple lattice polygon $p$ in $\mathbb{R}^{2}$, if $I$ is the number of lattices inside $p$ and $B$ is the number of lattices on the boundary of $p$, then the area ...
1
vote
1answer
19 views

Set Theory problem with unique numbers

Let $A_0$ be the set {$1, 2, 3, 4$}. Let $A_{i+1}$ be the set of all possible sums which can be obtained by adding two numbers in $A_i$ , where the two numbers do not have to be different. How many ...
-1
votes
1answer
47 views

For what reltively prime integers $a$ and $b$ does the expression $2ab$ an even numeric palindrome? [closed]

I currently doing some research on numeric palindromes. And I am stack with the problem: For what reltively prime integers $a$ and $b$ does the expression $2ab$ an even numeric palindrome? Since ...
1
vote
1answer
89 views

Monkeys Dividing Pile of Bananas

Three clever monkeys divide a pile of bananas. The first monkey takes some bananas from the pile, keeps three-fourths of them, and divides the rest equally between the other two. The second monkey ...
3
votes
4answers
214 views

When a set of consecutive numbers can be covered by differences between distinct integers?

I will start with an example. Suppose that I would like to cover the set $\{1,2,3\}$ by differences between three integers $m_1,\ m_2$ and $m_3$ in the following sense: $$ \{1,2,3\}=\{m_2-m_1,m_3-m_2,...
1
vote
0answers
35 views

When does longest permutation cycle = p-1? (where p is prime)

Taking p = 7 as an example, let c*r1 = r2 (p) If c = 2 we get 0 1 2 3 4 5 6 0 2 4 6 1 3 5 or (1 2 4) (3 6 5), so longest cycle is 3 < p-1 But for c = 3 we get 0 1 2 3 4 5 6 0 3 6 2 5 1 4 ...
3
votes
1answer
46 views

Count ways to take pots

There are N plant pots available in nursery placed in a straight line. Bob is planning to take few of these pots. But whatever number of pots he is going to take, he will take no two successive pots.(...
1
vote
1answer
54 views

What does this mean when interpreted mathematically, rather than this long phrase?

Quoted from: DANIEL A. GOLDSTON, JÁNOS PINTZ, and CEM Y. YILDIRIM, Primes in tuples I, Annals of Mathematics, 170 (2009), 819–862: Unconditionally, we prove that there exist consecutive primes ...
3
votes
1answer
45 views

Count rectangular frames

The grid is made up of $M \cdot N$ cells. The smallest cell formed is a square of unit area. Now we are given a hoarding of area $A$ units but there isn't any information on it's dimensions. It is ...
8
votes
1answer
314 views

How to solve $4x^3-3z^2=y^6$ in positive integers?

Solve in positive integers $$4x^3-3z^2=y^6$$ We are given that $\gcd (x,y) = \gcd (y,z) = \gcd (x,z) = \gcd (x,y,z) = 1$. I do not have the slightest idea how to even begin this question. ...
6
votes
4answers
175 views

Solve: $ab+bc+ca\mid (a+b+c)^2$

I couldn't make any progress on this problem, can anyone help? I found it's the same as: Find all integers $a,b,c$ such that $ab+bc+ca$ divides $a^2+b^2+c^2$. I found a solution $a=-b=1$, and $c$ ...
3
votes
2answers
245 views

Determine whether $712! + 1$ is a prime number or not

Let $n = 712! + 1$ If $n$ was a prime number then, by Wilson's theorem: $ (712!)! \equiv -1 \pmod{712}$ The double factorial makes it seriously more difficult... But We can require: $$712!! + 1 \...
8
votes
1answer
236 views

Proving that there are at least $n$ primes between $n$ and $n^2$ for $n \ge 6$

I was thinking about Paul Erdos's proof for Bertrand's Postulate and I wondered if the basic argument could be used to show that there are more than $n$ primes between $n$ and $n^2$. Is this approach ...
2
votes
1answer
58 views

Primitive roots for primes (Burton's text book)

On page 157 of Burton's elementary Number theory ,I am not sure if I understand the following reasoning:"Because 3 is a primitive root of 31 , any integer that is relatively prime to 31 is congruent ...
0
votes
1answer
193 views

Largest superprime number

Call a number n a superprime if every consecutive block of digits in n is also a prime. For example, the number 3727 contains the blocks 37 and 727, which are prime, but it also contains the blocks 72 ...
4
votes
1answer
730 views

1000 numbers on a blackboard

The numbers $1, 2, …,1000$ are written on a blackboard, in some order. Between every pair of consecutive terms, the absolute difference of the two terms is written between them, and then all the ...
3
votes
2answers
401 views

Deleting a Digit

Find the number of 5-digit positive integers n that have the following property: If we delete any digit in n, then we get a 4-digit number which is always divisible by 7. I did a little bit of modular ...
3
votes
2answers
69 views

Integer solutions to $7^a + 1 = 2^b$

I'm looking for integer solutions to the equation $7^a + 1 = 2^b$. There are two obvious answers: $a=0, b=1$ $a=1, b=3$ I believe that those are the only solutions, but I am unable to prove it. I ...
5
votes
2answers
58 views

Repeated operations on $(a,b)$

For each pair of integers $(a,b)$, define the sequence $S_{(a,b)}$ as: If $a_{n-1} < b_{n-1}$ then $(a_{n},b_{n}) = (2a_{n-1},b_{n-1}+1)$; otherwise if $b_{n-1} < a_{n-1}$ then $(a_{n},b_{n}) = ...
0
votes
1answer
39 views

Diagonalizing quadrics

I am doing the following exercise. Let $k$ be an algebraically closed field of characteristic not 2. a) Show that any quadratic form in $n$ variables can be "diagonalized" by changing coordinates to ...
-1
votes
3answers
102 views

If $a \equiv b$ (mod 2n), then $a^2 \equiv b^2$ (mod 4n)

How would I go about proving: If $a \equiv b$ (mod 2n), then $a^2 \equiv b^2$ (mod 4n)? I already tried proving $a+b = 2nk$ for some integer k, and that was pretty straightforward. But when I try to ...
-1
votes
2answers
402 views

Proof that if x is prime, then x+7 is composite. [closed]

Proof that if x is prime, then x+7 is composite. I do not know how to prove it. Can anyone help me to solve it? Thx
1
vote
2answers
55 views

A basic proof: $\forall a,b\in\mathbb{Z}$, if $a\left.\right|b$ then $a^2\left.\right|b^2$

I must state whether the following is true or false on my homework (yes, this is a homework problem, so I would appreciate it if you would only give hints or suggestions and not write out the total ...
1
vote
1answer
113 views

GCD of powers minus 1

So I'm working on a proof that for positive integers $a$, $b$ and $c$, $c>1$, that $GCD(c^a-1,c^b-1)=c^{GCD(a,b)}-1$. Not sure what I should think about doing first. My guess is I should start by ...
-2
votes
2answers
58 views

If $a,b,c\neq0$, prove that $ac\mid bc \iff a\mid b$ [closed]

How can I prove this question? If $a,b,c\neq0$, prove that $ac\mid bc \iff a\mid b$ Please help me
1
vote
2answers
54 views

If $n^m\mid m^n$ and $k^n\mid n^k$, prove $k^m\mid m^k$, $m,n,k\in \mathbb{Z}^+$

If $n^m\mid m^n$ and $k^n\mid n^k$, then $k^m\mid m^k$, $m,n,k\in \mathbb{Z}^+$ Aside from the definition of divisibility, can someone suggest theorems/facts that might be useful in proving this ...
0
votes
7answers
107 views

How to find $5^{2015}\pmod{11} $

How do I find this value. It's a very huge number to calculate. I do not know how to start here. Help will be appreciated. $$5^{2015}\pmod{11} ?$$ Thanks.
0
votes
0answers
57 views

Solving $x^p+ax^q+b=0$ with $x,a,b$ integer and $p-q>1$

Help solving $x^p+ax^q+b=0$, where $p,q,x \geq 0$ and $a,b \in\mathbb{Z}$. I am well aware of the complexity of this equation. However, I am mostly interested in the following particular case: Given ...
25
votes
5answers
2k views

The set $\{1,2,3,\ldots,n\}$, where $n \geq 5$, can be divided into two subsets so that the sum of the first is equal to the product of the second

A peer of mine showed me earlier today this problem, taken from a 7th grade math contest : Let $A=\{1,2,3,\ldots,n\}$; (where $n \geq 5$) prove that $A$ can be divided into two disjoint subsets ...