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

learn more… | top users | synonyms (1)

2
votes
1answer
29 views

Closeness of $n! \ x$ to integers for irrational $x$

This question came up in the comments to another question. Is there an irrational number $x$ such that, for sufficiently large $n$, the product $$ n! \ x $$ is arbitrarily close to an integer? More ...
5
votes
1answer
37 views

Pythagorean Triples : Is every positive integer $\gt$ $2$ part of at least one Pythagorean triple?

I was doing some basic number theory problems from Rosen and came across this problem: Show that every positive integer $\gt$ $2$ is part of at least one ...
0
votes
0answers
24 views

Divisors of Fermat numbers [duplicate]

For $n > 1$ let $F_n = 2^{2^n} + 1$ be a Fermat number and $a = 2^{2^{n - 2}}(2^{2^{n - 1}} - 1)$. Prove that any divisor of the Fermat number $F_n = 2^{2^{n}} + 1$ is of the form $k\,2^{n + 2} + ...
3
votes
4answers
22 views

Proving or disproving $c-d|p(c)-p(d)$ where $p$ is a polynomial.

I have $p(X)=\sum_{i=0}^{n}{a_iX^i}$, where $a_i\in\Bbb{Z}$. Let $c,d\in\Bbb{Z}$. Prove or disprove: $c-d|p(c)-p(d)$. I did some algebra but I can't think of a way to divide high power parts by ...
-3
votes
2answers
25 views

How can I prove $\phi(m)*\phi(n) = \phi(lcm(m,n))* \phi(\gcd(m,n))$ where $\phi$ is eulers $\phi$ function? [on hold]

Suppose m,n∈N how can i prove that $\phi(m)*\phi(n) = \phi(lcm(m,n))* \phi(\gcd(m,n))$ where $\phi$ is eulers $\phi$ function? If m and n have a common factor greater than 1. I have read up on the ...
0
votes
0answers
24 views

Let $R$ be an Euclidean ring. Prove that $\operatorname{lcm}(a,b) = \dfrac{ab}{\gcd(a,b)}$ for $a,b \in R.$

Let $R$ be an Euclidean ring. Prove that $\operatorname{lcm}(a,b) = \dfrac{ab}{\gcd(a,b)}$ for $a,b \in R.$ Does this proof work? Any criticism appreciated: We rewrite $\operatorname{lcm}(a,b) = ...
1
vote
1answer
14 views

Formula to map a variable to another?

For example, I have a variable $x$ that contains the value $100$, and assume I also have a variable $y$ that contains the value $300$ is there a method to decrement $x$ by some amount and have $y$ be ...
0
votes
2answers
27 views

Continued Fraction

I am working on the following question "Use the continued fraction $[1;0,1,1,2,1,1,4,1,1,6,1,1]$ to get an estimate for $e$." But I got stuck when I tried to compute $q_i$, since $a_1=0$ , $q_1 =0$. ...
1
vote
1answer
28 views

Value of the 3 prime numbers

Here's the question The 3 prime numbers $P,Q,R$ have a value where the product of themselves is 19 times larger than the sum of itself.Find $P^2+Q^2+R^2$. It means that $19(P+Q+R)=PQR$ Since ...
1
vote
0answers
26 views

Integral intersections between quadratic sequences

How can I find the integer solutions to: $$ x^2=\frac{1}{2} n (n+1) $$ By brute force I have found the solutions (6,8) (35,49) and (204,288) but then it gets harder. Note that the perfect squares ...
0
votes
1answer
54 views

Prove that for all $n\in \mathbb N$ $(n>1)$ the number $n^4+4^n$ is not prime. [duplicate]

Prove that for all $n\in\mathbb N$ $(n>1)$ the number $n^4+4^n$ is not prime. Can someone give me some pointers?
1
vote
4answers
31 views

Elementary theory of numbers and the phi function. [on hold]

Question: Let $n$ be a natural number, and suppose that $2 \phi(n) = n$. Prove that $n$ is a power of $2$.
0
votes
1answer
33 views

Floor inequality with prime

If $a$ and $b$ are positive integers and $a\ge b$ and $b$ is an odd prime, show that: $$\left\lfloor \frac{6a-1}{b}\right\rfloor+\left\lfloor\frac{a}{b}\right\rfloor\ge \left\lfloor ...
1
vote
2answers
24 views

Finding solutions to congruence equations

In my notes it has a theorem, stating: $ax\equiv b\mod m$ has solutions if and only if $\gcd(a,m)|b$. The proof going from right to left is: If $d=\gcd(a,m)$, $d|b \Rightarrow b=td$. We write ...
3
votes
0answers
30 views

What is the explicit formula (solution) to this recursively defined binary matrix?

My question concerns the following binary matrix (call it matrix $A$). Or rather the entire family of such matrices, for some number of columns $n$ and rows $2^n$. The ellipses indicate that the ...
1
vote
1answer
33 views

Real Numbers are Roots $r, s$.

Real numbers $r$ and $s$ are roots of $p(x)=x^3+ax+b$, and $r+4$ and $s-3$ are roots of $q(x)=x^3+ax+b+240$. Find the sum of all possible values of $|b|$. Using Vieta's Formulas, $r+s+x_1$ $=0$ ...
5
votes
1answer
83 views

Pythagorean Triples : Show that exactly one of $x$, $y$, and $z$ is divisible by $5$

I was doing some basic number theory problems from Rosen and came across this problem: Show that if $(x, y,z)$ is a primitive Pythagorean triple, then exactly one of $x$, $y$, and $z$ is divisible ...
5
votes
1answer
67 views

Solve $\phi(n) = 123456789 $ or prove there is no such $n$

I've solved it, but I'm interested to see if there is another way, because mine is computer assisted. Using the fact that if $p \mid n$ then $ p-1 \mid \phi(n) $, I find the set of divisors for ...
2
votes
3answers
28 views

Make $kt^2+(3k+1)t+4k+1$ constant?

Find $k$ such that $kt^2+(3k+1)t+4k+1=0$ is an identity (i.e. true for all $t$). E.g. $k=t+1$ doesn't work since you end up with a third degree polynomial in $t$ which determines $t$, making $t$ ...
0
votes
0answers
32 views

Is this curve an elliptic curve

I want to know whether curve $$x^3+21x^2+35x+7=4xy+4y^3$$ is an elliptic curve or not. If that is an EC so what is its Weierstrass form?
3
votes
1answer
36 views

$11$ positive integers-we can always make a cube number.

I have got the following task: Let us have $11$ positive integer, neither of them has a prime divisor greater than $29$. Prove, that we can always choose $a_1,...,a_k$ and next to them, ...
5
votes
3answers
86 views

Finding integer solutions of $m^2-n^5 = m - n$

How to list all integer solutions of $m^2-n^5 = m - n$ Here $m$ and $n$ are some positive integers. Also, I want to know the name of this type equations (if name exist). Regards Rosy
1
vote
2answers
34 views

The order of an element [duplicate]

The order of a unit $a \pmod m $ is the least $n \geq 1$ such that $a^n \equiv 1 \pmod m$. my question is : Is true that number and its inverse have the same order?
1
vote
2answers
33 views

proof verification(number theory)

I proved the following if p is an odd prime, then any divisor of Mersenne number is of form 2kp + 1. Proof: If q is a prime divisor of $M_p$ then qk = $2^p$ - 1 $\rightarrow$ $2^p$ $\equiv$ 1 (mod ...
5
votes
0answers
55 views

Equality by iteratively applying $(a,b)\rightarrow [(a+1,2b)\text{ or }(2a,b+1)]$?

I play a game starting with $2$ positive integers $a$ and $b$. At each step of the game I can double one of the integers and add $1$ to the other integer. Is there always a procedure for any ...
2
votes
1answer
38 views

Find all the primes that satisfy $p \mid 2^p - 1$

I just want somebody to verify that my work is correct. Find all prime numbers $p$ such that $p \mid 2^p - 1$. My claim is that there no such prime that satisfies this. If $pk = 2^p - 1$, we ...
1
vote
0answers
28 views

Finding the factors of integer x and its square

What is the the theorem or property that says that $\forall{}x\in{}Z$, the set of all integers, $x^2$ has the same factors as $x$, twice?
0
votes
1answer
22 views

Computing Large Number Modulo and Multiplicative Inverse

Prove that $3^{28}$ is a multiplicative inverse of $9^{34}$ modulo $17$, i.e. show that $3^{28}9^{34}\equiv 1\pmod {17}$. I really have no idea how to approach this example other than applying ...
1
vote
1answer
18 views

Maya Lists the Positive Divisors

Maya lists all the positive divisors of $2010^2$. She then randomly selects two distinct divisors from this list. Let $p$ be the probability that exactly one of the selected divisors is a perfect ...
1
vote
2answers
40 views

$\gcd(1000, 1000 - x)$ if $0 < x < 1000$, $x \in \mathbb{N}$.

Find $\gcd(1000, 1000 - x)$ if $0 < x < 1000$, $x \in \mathbb{N}$ and $x$ is coprime to $1000$. Since $1000 > 1000 -x$, it follows from Euclidean Algorithm, $$1000 = 1(1000 - x) + x$$ ...
0
votes
0answers
26 views

Determining if a rational number has a terminating decimal expansion (proof)

Theorem: $x=\frac pq$ is any given rational number, $n$ and $m$ are any whole numbers (including zero) which you can choose. a) If $q=2^n5^m$ is possible, $x$ has a terminating decimal expansion. ...
1
vote
3answers
31 views

How to prove that $n$ is a prime number iff for every integer $a$: $(a,n)=1$ or $n\mid a$

It seems like it's obvious because if $n$ is prime then its gcd with every number is $1$... But I understand that by intuition and don't know how to formally prove it... I'm confused.
1
vote
2answers
41 views

Euler Phi of a number

I saw an AIME problem where you took $\phi(1000)$ and then divided by $2$. The problem is here: http://www.artofproblemsolving.com/community/u244443h580665p4722095 $\phi(1000)$ gives you how many ...
6
votes
1answer
53 views

Pairs of integers $(a,b)$ such that $\frac{1}{6} =\frac{1}{a} + \frac{1}{b}$

How many pairs of integers are there $(a,b)$ with $a \leq b$ such that $$\frac{1}{6} =\frac{1}{a} + \frac{1}{b}$$ My attempt: Clearing fractions we get $$ab = 6(a+b)$$ $$ \Longrightarrow ...
1
vote
0answers
49 views

Blocks of consecutive natural numbers

Let a < b be natural numbers. Prove that every block of b consecutive natural numbers contains two distinct elements whose product is divisible by ab. Suppose now a < b < c are natural ...
0
votes
1answer
35 views

Prove $a^2+6a+1\perp 375$ for all $a\in \mathbb{Z}$.

Prove $A=a^2+6a+1\perp 375$ for all $a\in \mathbb{Z}$ I thought to write $375=3\cdot5^2$. So if $A$ is coprime with $3\cdot5^2$ they must share no prime factors. Then I test if $3$ or $5$ divide $A$ ...
2
votes
2answers
63 views

Prime $4n+3$ simple proof?

Let $p=4n+3$ be a prime. Prove that $\prod_{k=1}^{p-1}(x+k^2)\equiv (x^{\frac{p-1}{2}}+1)^2\pmod p$. Is there a simple proof that doesn't use say arithmetic in $\mathbb{Z}[i]$? My approach was to ...
0
votes
3answers
34 views

Postage stamp with $6$ and $7$ cents question

What is the largest postage in cents that cannot be paid exactly with an unlimited supply of $6$-cent and $7$-cent stamps? Any hint so that I can proceed?
0
votes
2answers
31 views

The Density Of The Real And Rationals

I am trying to get better understanding of the density property of the real numbers and the rational. As for the rational if we take for example $\frac{1}{100} $ and $\frac{1}{101}$ which number can ...
4
votes
1answer
48 views

Why is there only one group of order $n$ for some non-primes?

I would like to understand for which integers $n$ is there only one group of order $n$. (up to isomorphism). I understand that if $n$ is prime there is only one group of order $n$. In Sloane's OEIS ...
3
votes
3answers
95 views

Prove there exists $m > 2010$ such that $f(m)$ is not prime

Let $$f(x) = \sum_{i = 0}^n a_ix^i$$ be a polynomial with $a_i \in \mathbb Z, n > 0, a_n \neq 0$. Prove that there exists some natural number $m>2010$ such that $|f(m)|$ is not a prime number. ...
3
votes
2answers
67 views

“$111 \dots$ upto $3^n$ digits” is divisible by $3^n$

Prove that an integer of the form "$111 \dots$ upto $3^n$ digits" is divisible by $3^n$ My attempt For $n=1,$ $111$ is divisible by 3. Let $T_n=111...$ upto $3^n$ digits is divisible by $3^n$. ...
1
vote
3answers
72 views

Solve in non-negative integers: $m^2+n^2=1997 (m-n)$

Solve in $\mathbb{N}$:$$m^2+n^2=1997(m-n)$$ I try with quadratic equation or with factorising, but I have no idea what to do after that.
0
votes
1answer
25 views

A question in Number Theory - prove there exist m>2010 s.t f(m) is not prime [duplicate]

Let $$f(x)=\sum_{i=0}^n a_nx^n$$ be a polynomial with $$a_n \in Z,n>0,a_n\neq0$$ Prove that there exists some natural number $$m>2010$$ such that $$|f(m)|$$ is not a prime number. I tried to ...
0
votes
1answer
36 views

A question about primes, number theory [duplicate]

I tried to solve this question but without a success: Let $p$ be a prime number,and $p^2+2$ is also prime, prove that $p=3$. I tried to show $p^2+2$ as a product of numbers and then to show that ...
0
votes
2answers
30 views

Number Theory - Multiple of $36$ problem

Let $N$ be the greatest integer multiple of $36$ all of whose digits are even and no two of whose digits are the same. Find the remainder when $N$ is divided by $1000$. $$N = \overline{abcd....} ...
1
vote
1answer
64 views

Rational points on circle

I need help for the following questions. Give the necessary and sufficient condition for $r$ such that the circle $x^{2}+y^{2}=r^{2}$ passes the rational points. I know the obvious sufficient ...
0
votes
0answers
35 views

Is 1 the geometric mean of a positive number and its inverse? (same for -1 and neg numbers) [on hold]

Recently, I realized that all of multiplication in the interval [1, infinity) is contained as division in (0, 1} (same the other way around with neg numbers). It also seems to me that 1 is the ...
0
votes
1answer
30 views

if $a = 0 \mod p $ and $a \not = 0 \mod p ^2$

let $a = bc$ if $a = 0 \mod p $ and $a \not = 0 \mod p ^2$ with $p$ prime. what can we deduce? ($a,b,c \in \mathbb{Z}$) I have that if $a = 0 \mod p$ then either $b = 0 \mod p$ or $c = 0 \mod p$ (can ...
0
votes
5answers
72 views

Mathematical induction [duplicate]

Prove that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ where $n$ is a nonnegative integer. I have seen many questions on this site that contain the answer to this problem and I already know the solution, ...