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

learn more… | top users | synonyms (1)

0
votes
0answers
13 views

primitive root modulo prime powers [duplicate]

Suppose that $g$ is a primitive root modulo $p$. Show that, modulo $p^h$ for $h\geq 2$, every primitive root has the form $g'=g+np$ for a certain integer $n$. The proof of the previous statement ...
2
votes
0answers
35 views

Tetration of a number giving a complex number

Giving this power equation: $$S=\lim_{n\to\infty} {^n}x=-i$$ where the symbol $^nx$ means the tetration operator, we can write in a form not formally correct: $${\ ^{n}x = \ \atop {\ }} ...
-2
votes
1answer
22 views

Real polynomials from repunits to repunits ( Putnam 2007 A4) [closed]

Find all polynomials $ f$ with real coefficients such that if $ n$ is a repunit, then so is $ f(n).$
0
votes
0answers
11 views

Is this factorization of $\xi^3 \mp 1$ in $\mathbb{Z}[\omega]$ correct?

I'm trying to follow a proof of Fermat's Last Theorem for $n=3$ using the Eisenstein integers according to this paper. On page $6$ near the bottom the author gives the factorization $$\xi^3 ...
4
votes
4answers
82 views

If $p > 3$ is prime, then $12 $ divides $p^2 - 1$

First up, I know there are a lot of similar questions with 24, not 12. So bare with me please :) What is the Question? Consider the following numbers of the form $p^2 - 1$ where $p$ is prime. $$5^2 ...
0
votes
1answer
27 views

Smallest number starting with N divisble by every non zero digit of N

We are given a number N and we have to find the smallest number that starts with N and is divisble by every non zero digit of N.How can we do this ? If N is 13 then answer is 132 . According to the ...
1
vote
1answer
48 views

Not sure how to prove this statement by contradiction?

There is this a simple looking and intuitive statement but I am not sure how to start approaching this problem. Let $S=\{s_1,s_2,\ldots,s_n\}$, where $s_1,s_2,\ldots,s_n>0$ such that ...
2
votes
1answer
64 views

Is this polynomial time for greatest prime factor of odd numbers?

For natural numbers $n$ and $x,$ the number of $n^{th}$ roots that have $x$ in the whole numbers place can be represented as $(x+1)^{n}-x^{n}.$ For $p$ prime, $(x+1)^{n}-x^{n}-1\equiv0\bmod p$ iff ...
4
votes
1answer
56 views

Any more solutions to $m!!-n!=(2^k\pm1)^2$?

Factorial and double factorial $$m!!-n!=(2^k\pm1)^2$$ Where $m\ge1$ are all odd numbers $n\ge1$ are all integer numbers $k\ge0$ Is there more solution to this equation or this is the only ...
0
votes
1answer
11 views

Find all Dirichlet characters modulo $p$

In my elementary number theory class we define the following: Let $p$ be a prime, and let $\mathbb{Z}_p^*$ relatively prime residues modulo $p$. A Dirichlet character modulo $p$ is defined as a ...
19
votes
5answers
502 views

Is $11^2+12^2+13^2+14^2+15^2+16^2=1111$ special?

Is this pure coincidence or is this a special case of some well-known number-theoretic result? If the latter is true, is there some notable generalization? EDIT: Thanks to the interesting answers ...
1
vote
3answers
32 views

Find the remainder of $\sum_{i=0}^{99} 2^{i^2}$ when dividing by 7 and determine if the quotient is even or odd

I've recently had this problem in an exam and couldn't solve it. Find the remainder of the following sum when dividing by 7 and determine if the quotient is even or odd: $$\sum_{i=0}^{99} 2^{i^2}$$ ...
4
votes
1answer
61 views

Showing $n \mid \frac{x^{n}-y^{n}}{x-y}$

Let $x,y$ and $n$ be positive integers such that $n \mid (x^{n}-y^{n})$. How do I show that $\displaystyle n \mid \frac{x^{n}-y^{n}}{x-y}$. The best thing would be to show if $p^{k}\| n$, then ...
1
vote
1answer
64 views

Can composite numbers be uniquely written as a sum of two squares?

Let $X = a^2 +b^2$ where all the terms are positive integers and $X$ is a composite number and $\gcd(a,b)=1$ . Do there exist positive integers $c$ and $d$ other than $a$ and $b$ such that $X = ...
1
vote
1answer
37 views

Problem to find all $n$ in following situation [closed]

Find all $n>1$ such that $1^{n} + 2^{n} + 3^{n} +\cdots + (n-1)^{n}$ divisible by $n$. I'm not good at Number Theory so , give elementary answer.
3
votes
0answers
15 views

Is there a theory of “sums-of-squares residues”?

The theory of quadratic residues is long- and well-studied. Recall that, [somewhat simplified] if $x,a,b$ are integers, with $0 \le a < b$, such that $$x \equiv a^2\!\!\!\pmod{b},$$ then we say ...
1
vote
1answer
59 views

which odd integers $n$ divides $3^{n}+1$?

I don't understand this solution to this problem. Can anyone explain why d divides n?
0
votes
3answers
43 views

Given a range [a, b], how to find the x middle numbers?

Given a range [$a$,$b$], how can I find the $x$ middle numbers? For example: [$1$,$10$] Now I know that the middle $2$ numbers start with "$5$", but is there any way I can find the starting ...
3
votes
1answer
80 views

Is there any integer $n>1$ such that $3^n - 1$ is divisible by $2^n - 1$?

Is there any integer $n>1$ such that $3^n - 1$ is divisible by $2^n - 1$? I guess not. For every even integer $n$, we can show that $3^n - 1$ is not divisible by $2^n - 1$ because $2^n -1$ is a ...
-9
votes
1answer
76 views

Unconvincing way of showing$(-)\times(-1)=+$ [closed]

Showing why $(-)\times(-)=+$ Recalling rules of indices $b^0=1$ $\frac{b^m}{b^n}=b^{m-n}$ $b^m{\times}b^n=b^{m+n}$ We create a situation where it is involve the negatives of two numbers come face ...
1
vote
3answers
31 views

Let k $\in Z$, such that k $\ge$ -1. Then $k^2 + 1$ is not divisible by 3.

I had this on the exam a few months ago and I am doing it again just for review. I want to check if I did it right this time. Any comment would be appreciated! Proposition: Let k $\in Z$, such that ...
2
votes
1answer
33 views

Proving an identity involving floor function

Prove that : $$\left \lfloor \dfrac{2 a^2}{b} \right \rfloor - 2 \left \lfloor \dfrac{a^2}{b} \right \rfloor = \left \lfloor \dfrac{2 (a^2 \bmod b)}{b} \right \rfloor $$ Where $a$ ...
-1
votes
1answer
32 views

Show that a positive integer $a>1$ is a perfect square (i.e., the square of an integer)…

if and only is in the prime decomposition of $a$ all the exponent are even integers. I don't understand what the question is asking. If I'm interpreting this correctly....any $a>1$ such as 9 would ...
5
votes
2answers
228 views

Perfect numbers, please help

Perfect numbers:6, 28, 496, 8128, ... There is some interesting patterns, I just want to share it with you guy and ask some questions about. (1) $1+2+3=6$, perfect number 6 has 3 terms ...
-1
votes
0answers
18 views

exponents - known m and n, find m+n

Can anyone help me with this? I have hard time on it. Thank you very much! If m and n area positive integers, find the value of m+n if 3m + 2n is the largest three-digit number of this form?
0
votes
2answers
30 views

arrange numbers in order

Can anyone show me an easy way to solve this problem? Thank you very much! Problem: Arrange the numbers $a= 2^{88}, b= 3^{55}, c= 5^{44}, d= 7^{33}$ in order form least to greatest.
0
votes
3answers
47 views

If the sum of two $p$th powers is divisible by $p$, then it is divisible by $p^2$

If $p > 2$ is a prime and $p | (x^p + y^p)$, then show that $p^2 | (x^p + y^p)$ I have been stuck on this problem for a while now. (Though my textbook is prone to mistakes so the original ...
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
50 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
133 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
81 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
62 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
62 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 ...