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

learn more… | top users | synonyms (1)

1
vote
5answers
51 views

On non-existance square a natural number

let $n$ to be a natural number . Why there is not any integer $q$ such that $$n^2=6q-1.$$ My attempt: If there exists this $q$, then $n$ to be odd integer. Now let $n=2k+1$. Then $4k^2+4k+1=6q-1$. ...
0
votes
1answer
34 views

Why is $(p-2)! \textrm{ mod } p$ always 1 if $p$ is prime?

After running some test on my computer I found that when you have a prime $p$, then $(p-1)! \textrm{ mod } p$ always equals to $p-1$ and that $(p-2)! \textrm{ mod } p$ always equals to $1$. Why is ...
-5
votes
0answers
64 views

Writing a given number as the sum of four triangular numbers

"Every number can be written as the sum of three triangular numbers. Can you prove it?"< this is the problem I have so far that: there are lots of numbers like 5 that cannot be written as the sum ...
0
votes
1answer
35 views

Show that every $m$ which has the property that $a^{m-1}\equiv1 \pmod m$ for all $a$ with $(a,m)=1$ is square-free

$a^{m-1}\equiv1 \pmod{m}$ for all $a$ with $(a,m)=1$. I was able to prove the first part of the problem: show that for every $a$ such that $(a, 561)=1$, the congruence $a^{560} \equiv 1\pmod{561}$ ...
1
vote
4answers
159 views

Proving $\sqrt2$ is irrational

I used the method of contradiction by assuming that $\sqrt 2$ is a rational number. Then, by the definition of rational number, there exist two integers $p$ and $q$ whose ratio equals $\sqrt 2$. Thus, ...
2
votes
3answers
126 views

What is the last digit? [closed]

Consider all 100 digit numbers, i.e., those between $0$ and $10^{100} - 1$ (inclusive). For each number, take the product of non-zero digits (treat the product of digits of $0$ as $1$) , and sum ...
1
vote
2answers
24 views

Computing $x \pmod 5$ if we only know $x \pmod 7$

Let's say we have a number $n$ of which I know its value $x$ modulo $k$, then how can I calculate its value modulo $l$? For example; $n=271, k=7$, and $l=8$, so $x=271 \textrm{ mod } 7=5$. How can I ...
0
votes
2answers
29 views

Prove the generalized version of Euler's totient function.If $(a,b)=d$, then $\varphi(ab) = {d\varphi(a)\varphi(b)\over \varphi(d)}$

If $(a,b)=d$, then $$\varphi(ab) = {d\varphi(a)\varphi(b)\over \varphi(d)}$$ I thought about writing out $a, b$ and $d$ in their prime power decomposition, but then wasn't sure how to proceed.
-1
votes
1answer
36 views

Help on understanding this congruency

It is really simple but somehow I cannot connect the dots. If $p$ is an odd prime, how come $-1 \not\equiv 1 \pmod p$ ?
2
votes
1answer
52 views

Under which circumstances is the sum of $n$ $k$-th powers a $k$-th power?

Consider the sum $s$ of $n$ natural numbers each rised to a certain power $k$: $$s= a_1^k + a_2^k + \cdots + a_n^k.$$ Under which circumstances is $s = b^k$, for some $b \in \mathbb N$?
1
vote
2answers
102 views

Which mathematics theory studies structures like these?

Let $A_p$ be the set of all numbers whose prime factors are all in first $p$ prime numbers. example: $A_2= \{2,3,4,6,9,12,16,18,\ldots \}$ (all of these numbers can be generated by repeatedly ...
2
votes
1answer
61 views

Maximum value of $x$?

Let $x,y,z,v,w$ be real numbers and $$x+y+z+v+w=8,\qquad x^2+y^2+z^2+v^2+w^2=16.$$ Find the maximun value of $x$? I've solved this question by using the average of the numbers and got $x\leq ...
4
votes
1answer
65 views

If $\lfloor x^i\rfloor =i,i=1,2,3,\cdots,n$ find the maximum of $n$

Find the maximum $n$ for which there exist a real number $x$ such that $$\lfloor x^i\rfloor =i,\quad i=1,2,3,\ldots,n.$$ $\lfloor x\rfloor =1$,then $1<x<2$, $\lfloor x^2\rfloor =2$ then ...
0
votes
2answers
72 views

If the equation $\frac{ c^n - a^n+b^n+ d^n}{ab-cd} = z$ , then is it possible to prove that $\frac{d^n}{ab-cd} < z$ for all $n\ge3$?

Let us consider $a<b<c$ such that $(a+b)=(c+d)$ and $n\ge3$. It is possible to derive the values of $z$ for $n=3,\,4,\,5,\,6,\dots$ as follows $$\begin{split} z& = 3 (a+b)\\ &= 4 ...
1
vote
1answer
17 views

Least moving-overlapped subset of [1..n] that has the biggest natural density as possible.

Given a natural number n>1. I'd like to find a set $\phi = \{s_1,s_2, \cdots , s_m \} \subset \{1,2,\cdots , n \} $ with $m > 1$ that minimizes the following quantity: $$ S_{\phi} = ...
-1
votes
0answers
25 views

Does $kp +1$ form of divisors of :$ p^n+1 $ , for $n =2k >2$ and $1<kp +1<p^n+1$?

I would be interest to know if $kp +1$ can be the form of divisors of $p^n+1$ , for every even $n >2$ and : $1<kp +1<p^n+1$ How do I prove or disprove it ? Note :$k>0$: is integer ...
2
votes
1answer
29 views

Adding a power of two to a composite odd number

If I have a composite odd number $p_1$, then adding $2$ to $p_1$ will make it a number that is either a prime or that shares none of its factors: $p_2$. If I have the equation $p_1+2=p_2$ and I can ...
1
vote
1answer
80 views

Solving a little Diophantine equation:$(n-1)!+1=n^m$ [duplicate]

How can I solve this Diophantine equation: $$(n-1)!+1=n^m$$ with $n,m$ positive integers? From Wilson's theorem we can note that $n$ is a prime number. I proved to rewriting the equation ...
5
votes
5answers
135 views

How can we prove that $[ {c^n - (a^n+b^n)} + d^n ] / (ab-cd)$ will yield integers always?

Let us say $a<b<c$ and $(a+b)=(c+d)$ as well as $n\geq2$. Then it is found for all values of $n$ that $$ \frac{{c^n-(a^n+b^n)}+d^n}{ab-cd} \in \mathbb{Z} $$ Can you explain the reason ...
1
vote
4answers
31 views

Simple mod problem

It’s kind of a silly question but I can't find a simple way for finding the value of variable $d$ . $(5*d) \mod 8 = 1$ I normally just do this recursively by saying $d=d+1$ until I get the right ...
2
votes
1answer
28 views

For $x, y, n\in\mathbb{N}$ find $\lambda, \mu \in \mathbb{N}$ so that $\lambda x + \mu y = n$

We know from the Bézout's identity that for any $x, y \in \mathbb{Z}$ and $d := \gcd(x,y)$ there are $\mu, \lambda \in\mathbb{Z}$ so that $$\mu x + \lambda y = d\, .$$ We immediately see that if ...
59
votes
16answers
11k views

What is the smallest unknown natural number?

There are several unknown numbers in mathematics, such as optimal constants in some inequalities. Often it is enough to some estimates for these numbers from above and below, but finding the exact ...
3
votes
1answer
22 views

Prove that if $a\mid c$ and $b\mid c$ with $\gcd(a,b)=1$, then $ab\mid c$

I was thinking of using the fact that $\gcd(a,b) = 1$ implies that $ax + by = 1$ for some integers $x,y$. Then $acx + bcy = c$. I'm not sure how to proceed.
2
votes
3answers
85 views

Almost extended Euclidean algorithm - $ax+by=\gcd(a,b)+2$

So I have this equation: $$\eta+2=2g+1n,$$ where $g,n \in \mathbb{N}_{\geq 0}$ and $\eta \in \mathbb{N}_{>0}$. I want to find all possible integer-valued 2-tuples $(g,n)$ that satisfy this ...
0
votes
1answer
34 views

Does :$p(n)=2^{n²+n-1}-n²-n+1 $ abondant for all $n >1$?

let $p(n)=2^{n²+n-1}-n²-n+1 $ , and let $\delta(n)$ be sum of proper divisors of $n\in\mathbb{N}$. After some verifications according to the values of $n>1$ I noticed: $$\delta(p(n))> p(n)$$ ...
2
votes
1answer
32 views

What does notation $(a_1, a_2,\cdots, a_n)$ mean in book “The Classical Introduction to Modern Number Theory”?

I am reading the book on number theory and I have problems understanding this definition: DEFINITION: Let $a_1, a_2, \cdots, a_n\in\mathbb{Z}$; we define $$\left(a_1, a_2, \cdots, ...
4
votes
2answers
60 views

Product of digits

Find all natural numbers $x$ ($x$ in base $10$) so that the product of its digits is $x^2 - 10x - 22$. Here is what I did so far: I took two cases. The first case was considering one or more ...
4
votes
1answer
46 views

Name or OEIS Entry for a certain set of numbers?

I'm considering the set of positive integers $n$ such that the integers from $1$ to $n$ can be arranged in a line such that every two consecutive numbers add to a perfect square. The smallest ...
1
vote
1answer
43 views

When do three cubics form an arithmetic progression?

Are there any solutions to the diophantine equation $x^3+y^3=2z^3$ other than the trivial ones? What about $x^4+y^4=2z^4$? I think I remember these equations in one of Euler's work, but having ...
6
votes
1answer
67 views

Triangular numbers divided by $3$?

I came across this problem. I want to flip a triangle upside down and find the minimum number of moves to do so. These are all triangular numbers. And I have found that dividing the total number ...
0
votes
1answer
29 views

Number of grid points inside a triangle

I need to find a number of integer points inside a triangle with vertices $(0,0)$, $(A,0)$ and $(0,B)$, where $A$ and $B$ are positive integers. This problem can be reduced to the following ...
1
vote
1answer
30 views

Correctness of proof of generalized Euler's criterion

My lecture notes on quadratic residues were pretty sloppy, and I was trying to prove some theorems from class. I don't think I'm correct, though. Can anyone tell me if I'm wrong? Specifically, I think ...
1
vote
1answer
43 views

There exists a pair of positive ints $(m,n)$ such that $(m,n$ and $m+n)$ are all perfect squares

The only thing I figured to do was just to express these three guys.. $m =a^2$ ,$ n=b^2 $, and $m+n = a^2 + b^2$
1
vote
2answers
58 views

prove that if $a^n+1$ is prime then $a$ is even and $n=2^k$ [duplicate]

i managed to show that $a$ is a even (suppose it is, and then show that $2|a^n+1$) for the second part, I understand it has something to do with fermat numbers but couldn't solve. please help
0
votes
0answers
51 views

Solving a diophantine equation in an elementary way

I was trying to solve $x^2+1=y^3$ and found this answer: Does an elementary solution exist to $x^2+1=y^3$? but I'm having trouble understanding it. In the second last paragraph, why is there a ...
1
vote
1answer
50 views

How do I prove this claim?

Claim :Let $p$ be a prime and $m \geq 2$ be an integer. Prove that the equation $ \frac{ x^p + y^p } 2 = \left( \frac{ x+y } 2 \right)^m $ has a positive integer solution $(x, y) \neq (1, 1)$ if and ...
9
votes
1answer
89 views

An upper bound for Summative Fission numbers

I recently found OEIS entry A256504 and have been playing around with this sequence a bit. Its definition is: For a positive integer $n$, find the greatest number of consecutive positive integers ...
2
votes
3answers
61 views

Conjecture about linear diophantine equations

I've been dabbling with linear Diophantine equations and came across a rather interesting pattern that I would like to conjecture as true but I have no idea how about to come up with a proof. Let ...
0
votes
0answers
15 views

Pairwise relatively prime terms of a polynomial.

Suppose we have a polynomial $P(n)$ (with degree $\geq 2$) with integer coefficients and a positive leading coefficient. Is it true that there is a $n_0\in \mathbb{N}$ with the property: For every ...
2
votes
1answer
25 views

Finding a bound on double summation involving primes

I am reading a number theory proof of a result in which I am stuck on a bound.Suppose $p_1$ and $p_2$ are primes with the property that each $p_i$ satisfies $e^r \leq P_i <e^{r+1}$ and $P_1 \equiv ...
6
votes
0answers
55 views

Arrange Relatively Prime Numbers in a Circle

The question: In how many ways can you arrange the numbers $1$ to $8$ in a circle so that neighboring numbers are relatively prime? Can you generalize for $1$ to $n$? It's fairly easy to list ...
2
votes
0answers
20 views

Factorization by multiplying and representation as difference of two squares

Definition 1.$$R: \mathbb N \to \mathbb N: \ R(n) = \lceil\sqrt{n}\rceil^2-n.$$ This is the distance from $n$ to the smallest square greater or equal to $n$. Definition 2. Let $a$ be as positive ...
2
votes
2answers
21 views

unique number from 3D coordinates

Is it possible to get a unique real number from $(x,y,z)$ coordinates? I need to sort a list of coordinates so i am looking for a simple function that generates one unique number with which to sort. ...
1
vote
2answers
36 views

If all pairs of addends that sum up to $N$ are coprime, then $N$ is prime.

I think this must be a known theorem, but I've tried searching for it on google without much luck. I would state it as follows: If for all possible pairs of addends that sum to the same number N ...
7
votes
4answers
99 views

Find the number of positive integers solutions of the equation $3x+2y=37$

Find the number of positive integers solutions of the equation $3x+2y=37$ where $x>0,y>0,\ \ x,y\in \mathbb{Z}$ . By trial and error I found $$\begin{array}{|c|c|} \hline x & y \\ ...
1
vote
5answers
87 views

Modular arithmetic , calculate $54^{2013}\pmod{280}$.

How do you calculate: $54^{2013}\pmod{280}$? I'm stuck because $\gcd(54,280)$ is not $1$. Thanks.
4
votes
10answers
290 views

Why does the largest $x$ such that $a$, $b$ divided by $x$ leave the same remainder equal $a-b$?

Suppose two numbers $a$ and $b$ as, $a=kq_1+r_1=3\times 17 + 1 = 52$ and $b = kq_2+r_2=3 \times 15 +1=46$. It is clear that $52$ and $46$ leave the same reminder 1 when divided by $3$, because I ...
3
votes
3answers
112 views

Find all Integral solutions to $x+y+z=3$, $x^3+y^3+z^3=3$.

Suppose that $x^3+y^3+z^3=3$ and $x+y+z=3$. What are all integral solutions of this equation? I can only find $x=y=z=1$.
0
votes
3answers
42 views

Nontrivial integer solution of simple cubic equation

Are there any nontrivial (except (0,0)) integer solution of the following equation? $a^3+b^3-(a+b)^3+a^2+b^2+(a+b)^2=0$
1
vote
1answer
74 views

Confusion on Mersenne Numbers

One fundamental theorem on Mersenne Numbers states: If $q$ is a prime of the form $8k+7, q|M_{(q-1)/2}=2^{(q-1)/2}-1$. Let $q=7+768z$, So ...