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

learn more… | top users | synonyms (1)

1
vote
3answers
42 views

Solving $rX_1^2+sY_1^2+tZ_1^2=rX_2^2+sY_2^2+tZ_2^2$ completely in integers

Given pairwise relatively prime integers $r,s,t$, I’m looking for a complete solution (i.e., integer parameterization or similar) for the Diophantine equation $$ ...
1
vote
1answer
34 views

Polynomial having all integral coefficients $P_n(a)=b$ and $P_n(b)=c$ and $P_n(c)=a$

Let $a,b,$ and $c$ denote three distinct integers, and let $P_n$ a polynomial having all integral coefficients. Show that it is impossible that $P_n(a)=b$ and $P_n(b)=c$ and $P_n(c)=a$. I started ...
0
votes
3answers
40 views

Modulo Equations

I am trying to solve a problem involving modulo arithmetic but I am not sure what method to use as I have never done this style of question before nor do I have any examples to work from. The ...
0
votes
2answers
23 views

Equation between the greatest common divisor and the least common multiple

the symbols $(a,b,c,...,g)$ and $[a,b,c,...,g]$ are denote the greatest common divisor and the least common multiple, respectively for the positive integers $a,b,c,...g$. Example : $(3,6,18)=3$ and ...
0
votes
0answers
36 views

Prove that $\frac{a^2+b^2}{1+ab}$ must be a perfect square [duplicate]

if $a$ and $b$ are positive integers and if $1+ab$ divides $a^2+b^2$ then prove that the quotient must be a perfect square. Let $$\frac{a^2+b^2}{1+ab}=k$$ where $k$ is some positive integer now ...
2
votes
1answer
51 views

Use of modular arthemitic to prove identity

While studying primes that are either $2^n+1$ or $2^{n}-1$, I noticed this relationship. $2^{(n-1)/{2}}-(-1)^{(n^{2}-1)/{24}}\equiv 0\mod n$ iff $n$ is prime for $n\ge5$. My question is, how can I ...
0
votes
0answers
39 views

If $m$ is a positive integer, show that $(ma, mb) = m(a, b)$ .

What I did was let $(a,b)=d$. Then writing the linear combination, $max+mby=md$. Then, to prove that any common divisor of $ma$ and $mb$ can divide $md$. I let $ma={ma_1}{c}$ and $mb={mb_2}{c}$. Then, ...
1
vote
5answers
121 views

Show that $n^2+11n+2$ is not divisible by $113^2$ ( n is integer)

Show that $n^2+11n+2$ is not divisible by $113^2$ ( n is integer) It's obvious that if we show $113$ doesn't divide $n^2+11n+2$ we are done...
1
vote
1answer
85 views

LCM of consecutive numbers

Given L = LCM(1,2,.....,n) We need to find the largest 'm' such that m<=n and LCM(m,m+1,.....,n) = L Any process to do so? eg. LCM (1,2,3,4,5) = 60 and LCM (3,4,5) = 60 So, for n=5 ...
2
votes
1answer
31 views

To Prove the relation between HCF and LCM of three numbers

if $p,q,r$ are three positive integers prove that $$LCM(p,q,r)=\frac{pqr \times HCF(p,q,r)}{HCF(p,q) \times HCF(q,r) \times HCF(r,p)}$$ I tried in this way; Let $HCF(p,q)=x$ hence $p=xm$ and $q=xn$ ...
3
votes
3answers
134 views

If $p\nmid a$ (where $p$ is a prime), then prove that there is an integer $b$ such that $a\mid (p^b -1)$

If $p\nmid a$ (where $p$ is a prime), then prove that there is an integer $b$ such that $a\mid (p^b -1)$ . Though the thing seems easily verified through trivial put and check solutions, but I ...
1
vote
2answers
54 views

Find ABC given that the other five possible permutations of its digits add up to 3194

I was going through Terence Tao's solving mathematical problems,A Personal Perspective . I was trying to solve the following problem which is exercise 2.1 on pg. 13, in the chapter Examples in Number ...
4
votes
1answer
57 views

Does $c(f) = \gcd(\{ f(n) | n \in \mathbb{Z} \})$?

Consider $\sum_{i = 0}^n a_i x^i \in \mathbb{Z}[x]$. Recall that the content of a polynomial is the gcd of its coefficients. I'm wondering whether the content is equal to $\gcd ( \{ \sum_{i = 0}^n a_i ...
3
votes
3answers
52 views

How to demonstrate that $2^{2^n - 2} + 1$ is a nonprime number?

This, considering $n ≥ 3$. I have tried by induction; I suppose that it's true for all n less than or equal to k (and greater than or equal to 3), but then I stride when I go to prove for n = k + 1. ...
1
vote
1answer
56 views

Prove that $4n+2=x^2+y^2+z^2$ for some odd $x,y$ and even $z$

Show that for all $n\in \mathbb{N}$, exists $x,y,z \in \mathbb{N}$, such that $x,y$ are odd and $z$ is even, such that $4n+2=x^2+y^2+z^2$. I started by using the fact that every natural number has a ...
2
votes
5answers
82 views

Find all positive integers $n$ such that $n^2+n+43$ becomes a perfect square

Find all positive integers $n$ such that $n^2+n+43$ becomes a perfect square. Since $n^2+n+43$ is odd,if it's a perfect square it can be written as: $8k+1$,then: $$n^2+n+43=8k+1\Rightarrow\ ...
2
votes
1answer
39 views

Show that $a$ is a quadratic residue mod $p$ if and only if a set has even cardinality

Let $p$ be an odd prime and let $a$ be an integer that is not divisible by $p$. Show that $a$ is a quadratic residue mod $p$ if and only if $$|\{a, 2a, . . . ,((p − 1)/2)a\} ∩ \{(p + 1)/2 , ...
2
votes
0answers
20 views

Find series for spiraling over matrix of size $nxn$ filled with numbers from 1 up till and including $n^2$

The following question exists: When starting from the number 1 and adding four numbers on each row a $4x4$ matrix is formed as follows: ...
-2
votes
1answer
26 views

Effective upper bound for a sum over prime numbers

Fix $y$ a positive real number. Is there an effective bound for the following sum i.e a positive constant B such that $$\sum_{p>y}\sum_{\nu \geq 4} \frac{1}{p^{9\nu/32}} \leq B.$$ Many thanks.
1
vote
1answer
64 views

$P$ the set of primes $p$ for which $q$ is a quadratic residue modulo $p$. Show that there is $n$ and $φ(n)/2$ arithmetic progressions such that..

$q$ is a prime and let $P$ be the set of primes $p$ for which $q$ is a quadratic residue modulo $p$. Show that there is an integer $n$ and $φ(n)/2$ arithmetic progressions with difference $n$ each, ...
0
votes
1answer
38 views

Base 8 to X(Base 16) conversion

475.641(Base 8) to X(Base 16) Answer is 13D.D08(Base 16) My attempt: 27BA1(Base 16) Which step I had missed? Thanks.
4
votes
0answers
64 views

Multiplicative group of $\mathbb{Z}/p\mathbb{Z}$ for a prime $p$ is cyclic

This question has been explored thoroughly, and in more generality too. For general fields, I am aware of standard proofs. However, I was naively trying to prove it in the simple case of prime $p$ ...
1
vote
0answers
51 views

Find all natural numbers of the form $2^n$ whose all digits are even

Find all natural numbers of the form $2^n$ whose all digits are even. For example: $2, 4, 8, 64, 2048$ (I believe they are the only such numbers). For $n \geq 11$, so far, I can prove that the last ...
2
votes
1answer
39 views

Dividing primes

Let $p_1,\dots , p_{n+1}$ be distinct primes, let $\alpha_1, \dots , \alpha_n$ be integers, and let $a,b$ be integers. Suppose we had the equation: $$b^2p_{n+1} = a^2p_1^{\alpha_1}\dots ...
2
votes
3answers
95 views

If sum of n natural number is 20 then what is their max. product?

If sum of n natural number is 20 then what is their max. product ?
0
votes
1answer
49 views

If n is a positive integer that is not square free

Determine if the statement is, in general, true or false. Recall that a universal statement is true if it is true for all possible cases while it is false if there is even one counterexample. Be ...
2
votes
0answers
67 views

$m^2+n^2$ and $m^2-n^2$ cannot both be squares [duplicate]

I need to show that there aren't any $m$ and $n$ such that $m^2+n^2$ and $m^2-n^2$ are both squares. First of all, assume without loss of generality that $m$ and $n$ are co-prime, since otherwise we ...
0
votes
1answer
49 views

Proving that $n$ is a Carmichael number

Determine if the statement is, in general, true or false. Recall that a universal statement is true if it is true for all possible cases while it is false if there is even one counterexample. Be ...
2
votes
1answer
25 views

when p is sum of two square integer, prove (a/p) which is legendre symbol = 1

Let a,b be integers and p be an odd prime. if $p$=$a^2+b^2$ and a is odd, prove $(a/p)$ which is legendre symbol = $1$ what i have done is that : because p and a are odd, b must be even and p is ...
0
votes
1answer
55 views

find the smallest integer value of $p$ for which $\sqrt {480p}$ is an integer

Full Question: 180 can be expressed as a product of its prime factors as $180=2^2\times3^2\times5$, find the smallest integer value of p for which $\sqrt {480p}$ is an integer I'm stuck here ...
2
votes
2answers
115 views

When is $\frac{a}{n} = n^a$ true?

Title says it all really, I am trying to figure out if theres a situation where $\frac{a}{n} = n^a$ is true or if this is impossible. This is not realy from somewhere, just for the sake of curiosity. ...
-1
votes
2answers
45 views

$x^{2} \equiv-1\ \pmod p$ has a solution if and only if $p\equiv 1\ \pmod 4$ [duplicate]

If $p$ is a prime. Then $x^{2} \equiv-1\ \pmod p$ has a solution if and only if $p\equiv 1\ \pmod 4$. Please explain in the easiest way.
6
votes
1answer
78 views

Show that among any consecutive $16$ natural numbers one is coprime to all others

Show that among any consecutive $16$ natural numbers one is coprime to all others. Is it useful to use the division algorithm on $16$? $16k,16k+1,16k+2,...16k+15$
3
votes
0answers
17 views

$R=\{ m+nr\sqrt{2} \mid m,n \in \Bbb Z \}$ and $I_{a,b}=\{ ma+n(b+r\sqrt{2}) \mid m,n \in \Bbb Z \}$

Let $r$ be a natural number and $R=\{ m+nr\sqrt{2} \mid m,n \in \Bbb Z \}$. We can show that $R$ is a subring of the ring $\Bbb Q [\sqrt{2}]$. My questions are as follows: $(1)$ Suppose that a ...
4
votes
2answers
73 views

Question from Mathcounts competition

The least positive integer that is divisible by $2, 3 ,4,$ and $5,$ and is also a perfect square, perfect cube, $4^{th}$ power, and $5^{th}$ power, can be written in the form $a^b$ for positive ...
0
votes
1answer
16 views

Worded linear congruence problem-Days/Years

The Melbourne cup is run every year on the first Tuesday in November. The US presidential elections are held every four years on the day after the first Monday in November. George W. Bush was elected ...
3
votes
2answers
47 views

Show that $a^{13} \equiv a \pmod{3 \cdot 7 \cdot 13}$.

Show that $a^{13} \equiv a \pmod{3 \cdot 7 \cdot 13}$. I want to know if my attempt is correct. First $a^{13} \equiv (a^3)^4 \cdot a \equiv a^4 \cdot a \equiv a^3 \cdot a^2 \equiv a \cdot a^2 ...
0
votes
2answers
54 views

Find an integer function $f(n)$ that is even for $n\not \equiv 2\bmod 3$, and odd for $n\equiv 2\bmod 3$

Does a function $f:\mathbb{N}\to\mathbb{N}$ that satisfies $$ f(n) \equiv \begin{cases}0 \bmod{2}, & n\equiv 0,1\bmod{3} \\ 1\bmod{2}, & n\equiv 2\bmod{3} \end{cases} $$ exist (with an ...
-4
votes
1answer
35 views

No solution in naturals

Prove that there is no pair $(x,y)$ of positive integers such that $$axy-b=x(x-c)+y(y-d)$$ where $a,b,c,d$ are positive integers such that $a>b>(\frac{1}{2} \cdot max\{c,d\})^2$.
1
vote
0answers
19 views

How is calculated the density of the 2-almost primes sequence?

According to the definition of sequence density at Wolfram's site: Let a sequence $\{a_i\}_{(i=1)}^{\infty}$ be strictly increasing and composed of non negative integers. Call $A(n)$ the number of ...
0
votes
1answer
46 views

Characterize the integers $a,b$ satisfying: $ab-1|a^2+b^2$

Let $a$ and $b$ be two positive integers such that $ab-1|a^2+b^2$. Show that $\frac{a^2+b^2}{ab-1}=5$.
0
votes
0answers
25 views

Fractions ( k / p - k ) ≠ prime/prime imply gcd(k / p - k) = 1

Prove that for every $$k ∈ \{{ 1, 2, 3, ..., \frac{(p - \frac{1 - (-1) ^ p}{2} )}{2}}\}\E $$(E is the set of even numbers) such that $$\frac{k}{p - k} \neq \frac{prime}{prime}$$ implies that for all k ...
1
vote
1answer
37 views

How to split congruences so moduli are prime powers?

If I have the linear congruence x=5 mod 84, is this equal to x=2 mod 3, since 3|84? This seems too easy.
1
vote
0answers
20 views

How Euclidian Algorithm for division works with algebric expressions?

I am attending an introductory Number Theory class for Computer Science focused on cryptography. I have done some exercises with integers number but I have two exercises in which appears algebric ...
0
votes
0answers
40 views

congruence solution

Determine is, in general, true or false. Recall that a universal statement is true if it is true for all possible cases while it is false if there is even one counterexample. Be prepared to prove that ...
4
votes
1answer
63 views

If $a$ is not divisible by $7$, then $a^3 - 1$ or $a^3 + 1$ is divisible by $7$

Determine is, in general, true or false. Recall that a universal statement is true if it is true for all possible cases while it is false if there is even one counterexample. Be prepared to prove that ...
0
votes
0answers
62 views

If $m =4^{n +1}$ with $n>0$ and m is prime then $3^\frac{m-1}{2}$ =-1(mod m)

Determine is, in general, true or false. Recall that a universal statement is true if it is true for all possible cases while it is false if there is even one counterexample. Be prepared to prove that ...
0
votes
1answer
30 views

Let p be a odd prime, If ord p (a) = h and h is even, then a^(h/2)= -1 mod p

Determine is, in general, true or false. Recall that a universal statement is true if it is true for all possible cases while it is false if there is even one counterexample. Be prepared to prove that ...
0
votes
1answer
18 views

Only one prime factor of $2^{2^{k}}-1$ of the form $3\pmod{4}$

Consider the number $N= 2^{2^{k}}-1$ for $k\geq 1$. Then is it true that for all $k \in \mathbb{N}$, $N$ has exactly one prime divisor which is $3 \pmod{4}$ and that being $3$. Some examples which I ...
-1
votes
0answers
24 views

Solutions to a congruence in a product of cyclic groups

I'm trying to answer the following question. How many solution are there for the equation $x\equiv 0 \pmod p$ in $\mathbb{Z}_{p}\times \mathbb{Z}_{p^{3}}\times \mathbb{Z}_{p^{5}}$