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

learn more… | top users | synonyms (1)

1
vote
2answers
159 views

Set of natural number solutions to $x^2+y^2=z^2$

I know that there are infinitely many solutions to the equation $x^2+y^2=z^2$ $x,y,z\in N $ but if we restrict the numbers to {1,2,3,4...n}, then how many triplets (x,y,z) exist? Asymptotical ...
4
votes
1answer
206 views

$x^2+y^2=z^2(1+xy)$ prove $z=\min \{x;y;z\}$ (with $x,y,z \in \mathbb{Z^+}$)

$x,y,z \in \mathbb{Z^+}$ such that $x^2+y^2=z^2(1+xy)$. Prove $z=\min \{x;y;z\}$ $$x^2+y^2=z^2(1+xy) \iff xy = \frac{x^2+y^2} {z^2} - 1$$. Assum $z>y \implies xy < x^2/z^2$, we have $xy \in Z ...
1
vote
4answers
501 views

Euclidean algorithm and assumption of division algorithm

From university notes: "In Euclidean we use the division alogorithm we assume that m | a and m | b iff ...
5
votes
1answer
103 views

Showing there exists infinite $n$ such that $n! + 1$ is divisible by atleast two distinct primes

This is a homework question. I know there exists infinitely many primes. Let $n = p-1$ and so by Wilson's theorem we know there exists atleast one prime $p$ that divides $n! + 1$. I used ...
3
votes
1answer
116 views

Solve the congruence$x^3+4x+8\equiv{0}\pmod{15}$

Solve (if possible)the congruence involving polynomial $x^3+4x+8\equiv{0}\pmod{15}$ My work: Since $15=3\cdot5$, we have $x^3+4x+8\equiv{0}\pmod{3}$ and $x^3+4x+8\equiv{0}\pmod{5}$ In ...
5
votes
6answers
2k views

Prove that if $n$ is a composite and $p \gt \sqrt[3]n$, then $n/p$ is a prime.

Also, $p$ is the least prime factor of $n$. I'm trying to do this by way of contradiction. Since $n$ is a composite, $n = pq$, for some $q \in \Bbb Z$. So, we have $p | n$, $q|n$ and $q = \frac ...
1
vote
1answer
496 views

Solve the congruence $x^3+2x-3\equiv{0}\pmod{45}$

Solve (if possible)the congruence involving polynomial $x^3+2x-3\equiv{0}\pmod{45}$ My work: Since $45=3^2\cdot5$, we have $x^3+2x-3\equiv{0}\mod(3)$ and $x^3+2x-3\equiv{0}\pmod 5$ In ...
2
votes
2answers
278 views

Finding the smallest positive integer $N$ such that there are $25$ integers $x$ with $2 \leq \frac{N}{x} \leq 5$

Find the smallest positive integer $N$ such that there are exactly $25$ integers $x$ satisfying $2 \leq \frac{N}{x} \leq 5$.
0
votes
1answer
94 views

demonstration number theory

Let be $a, b, c$ real numbers such that: $$a+b+c \neq 0 \mbox{ and } ab+bc+ca \mbox{ is rational. }$$ Prove that $a^4+b^4+c^4$ is rational if and only if $abc$ is rational
7
votes
4answers
342 views

Elementary Number Theory Congruence Proof

I’m stuck on the following number theory problem: Let $a$ and $b$ be integers not divisible by the prime number p. If $a^{\space p} \space \equiv \space b^{\space p} \space \pmod p,\;$ prove ...
0
votes
2answers
102 views

Prove that if $m = 1 \pmod {\varphi (n)}$ and $(a, n) = 1$ then $a^{m} = a \pmod n$

Prove that if $m = 1 \pmod {\varphi (n)}$ and $(a, n) = 1$ then $a^{m} = a \pmod n$, where $\varphi$ is Euler's function
1
vote
1answer
60 views

Are there infinitely many primes of the form $n^k+l_0$ for fixed $l_0$ when $(n,k)$ runs through the $\mathbb N\times ({{\mathbb N}\setminus\{1\}}$)?

I do not know if this what I am going to ask is immediate consequence of something known but if not it may have an easy answer which I do not see, so any help would be great. Let us define sequence ...
2
votes
2answers
63 views

$k=2^n + 1$ is prime $\rightarrow n=2^m$

I am struggling with this proof. I want to prove the contrapositive, $n=2^ab \rightarrow 2^n + 1$ is composite. My professor gave me a hint, $n=2^ab$, $b=2r+1 \ge 3$ $\rightarrow$ $2^{2^a}+1 | ...
4
votes
2answers
418 views

$\mathrm{lcm}(1, 2, 3, \ldots, n)$?

I want to find $\mathrm{lcm}(1, 2, 3, \ldots, n)$ where $2 \le n \le 10^8$ . I'm trying to find a formula . Please Help .
1
vote
1answer
45 views

Prove if $a,b,c$ are integers and $9\mid a^2+b^2+c^2$ then $9\mid a^2-b^2$ or $9\mid a^2-c^2$ or $9\mid b^2-c^2$

Attempting to help a non-math major answer this question. Unsure why the problem allows the option for "$9\mid a^2-b^2$ or $9\mid a^2-c^2$ or $9\mid b^2-c^2$". Also we have to prove without using ...
4
votes
5answers
132 views

Assume $n$ is even. Prove that $323$ divides $20^n+16^n-3^n-1$.

I'm unclear what is the best method to teach this with minimum math experience.
0
votes
2answers
65 views

Determine with a proof the largest number which can be written as a product of natural numbers which have sum 2012

I'm having trouble finding the largest number and proving it.
0
votes
1answer
957 views

Prove that if $n$ is a composite, then $2^n-1$ is composite. [duplicate]

Not sure if I'm doing this correctly but this is what I've done: Assume that $n$ is composite and suppose $2^n-1$ is a prime for $n \gt 2$. Then, $2^n-1 = 2k$ for some $k \in \Bbb Z $, $\forall n$. ...
-2
votes
1answer
96 views

Solve for $x$: $\sqrt{12} - \sqrt[3\leftroot1]{720} = \sqrt{x}$

I want to solve for $x$ Here's the question $$\large \sqrt{12} - \sqrt[3\leftroot1]{720} = \sqrt{x}$$ I need to find the value of $x$ Help!
3
votes
1answer
274 views

Diophantine equations - Perfect square and Perfect cube related

Solve following Diophantine equations: $1) \ a^3-a^2+8=b^2$ 2) $a, \ b,\ c \in \mathbb{Z^+}$$$\frac{a^3}{(b+3)(c+3)} + \frac{b^3}{(c+3)(a+3)} + \frac{c^3}{(a+3)(b+3)} = 7$$ 3) $a^3-8=b^2$ In ...
0
votes
4answers
225 views

Using modular congruence to solve equation

Show that there are no intergers $x$ and $y$ such that $P(x,y)=x^2-5y^2=2$ Hint from professor: Consider the equation in a convenient $\mod (n)$ so that you end up with a polynomial in a single ...
1
vote
2answers
618 views

Solving non-linear congruence

$x^2+2x+2\equiv{0}\mod(5)$, $7x\equiv{3}\mod(11)$ My attempt: $x^2+2x+2\equiv{0}\mod(5)$ $(x+1)^2\equiv-1\mod(5)$, we have $x+1\equiv-1\mod(5)$ since $5$ and $11$ are coprime. We have a solution ...
3
votes
4answers
231 views

Modular arithmetic polynomial question

Is it possible to find all polynomials of the form $ an^2 + bn +c $ where a,b, and c are integers and such that $$ a+b+c \equiv 31 \pmod{54} $$ $$ 4a+2b+c \equiv 3 \pmod{54} $$ $$ 9a+3b+c ...
0
votes
2answers
108 views

For which $\alpha$, $\alpha xy - 1|(\alpha x^2-1)^2 $ implies $x=y$?

Suppose $\alpha\in \mathbb{N}$, and $$A=\{(x,y)\in \mathbb{N}^2 \mid x\ne y,\quad \alpha xy - 1|(\alpha x^2-1)^2 \}$$ is the relation $A$ symmetic? When is it empty? For more information please ...
-3
votes
4answers
82 views

The prime numbers that divide $10^4-1$

How to find the prime numbers that divide $10^4-1$
1
vote
1answer
94 views

Like Diophantine equation

The equation $x^n - ny^x-nxy$ = $0$ has solution set $(n, x, y) = (1, 1, \frac12), (2, 1, \frac14), (3, 1, \frac16), \ldots$ I would like to know/learn the following (Kindly discuss) 1) If we ...
1
vote
1answer
115 views

Proving $g(\chi\rho)^6=(-1)^{(p-1)/2}p(\overline{\chi(2)J(\chi,\rho)})^4$, from Ireland and Rosen.

Suppose $p\equiv 1\pmod{3}$, $\chi$ is a cubic character, and $\rho$ is the quadratic character on $F_p$. If $\chi\rho$ is a character of order $6$, why does the Guass sum ...
0
votes
2answers
60 views

Congruence relationships.

I need to prove (or disprove but I don't think that's the case) that: if $ab \equiv 0$ (mod $n$), then $ a\equiv 0$ (mod $n$) or $b\equiv0$ (mod $n$) I know that $ab\equiv 0$ (mod $n$) ...
2
votes
2answers
115 views

Integer solution to equation

Does $$b =a-23\sqrt 3 \sqrt a+432$$ have infinitely many integer solutions? $a = 3$ gives one; $a = 27$ gives one; $a = 27\times 9$ gives one.
2
votes
4answers
1k views

Fermat's Little Theorem Problem

How can we use Fermat's Little Theorm to find the least non-negative residue modulo m with numbers with large exponents. For example, how would one find the least non-negative residue modulo m with ...
3
votes
4answers
129 views

Find $a$, $b$, and $c$ so $a \mid bc ~$ but $a \nmid b \space $ and $a \nmid c$

I'm working out of the text "Elementary Number Theory" by James K. Strayer and I've run into the following problem: Find integers $a$, $b$, and $c$ such that $a \mid bc ~$ but $a \nmid b \space $ ...
22
votes
1answer
233 views

Do numbers of this form have a name?

$$48625 = 4^{5} + 8^{2} + 6^{6} + 2^{8} + 5^{4}$$ Notice that the digits of the number are in digit order, while the exponents are the digits of the number in reverse order. Do numbers of this form ...
1
vote
3answers
46 views

inequality with one number and a sum of numbers

Let $x_1, \ldots, x_n $ be non-zero real number, such that $\sqrt{x_1^2 + \cdots + x_n^2}=1$. Show that for any $i = 1, \ldots, n$, $$|x_i| \leq \sqrt{\frac{x_1^2 + \cdots + x_n^2}{n}}= ...
0
votes
1answer
71 views

Primes $n=\overline{10101\cdots01}$ with $k$ ones.

Find all primes $n=\overline{10101\cdots01}$ with $k$ ones. The number is in standard base 10.
1
vote
2answers
259 views

How to find the gcd of this polynomial?

What would the GCD of $3n + 2$ and $4n + 3$ be using Euclid's algorithm
4
votes
1answer
701 views

Period of repeating decimals

Note: This question is base sensitive. Therefore, assume we have fixed a base $b$. By abuse of terminology, I will still use the word "decimal". This question revolves around the period of repeating ...
3
votes
2answers
351 views

$n|(n-1)!$ for all composite numbers $n>4,n\in \mathbb{N}$

$n|(n-1)!$ for all composite numbers $n>4,n\in \mathbb{N}$! Can anyone provide an elementary general or even combinatorial proof of this. Thanks in advance.
4
votes
1answer
63 views

How can the formula be found for this problem?

We have a truck that we need to completely fill up with merchandise. We have an infinite supply of merchandise of dimension $1\times1\times1, 2\times2\times2, 4\times4\times4, 8\times8\times8, ...
1
vote
0answers
45 views

Group extension of the natural numbers? What is this called?

Let $\{g_1, ... , g_n\}$ be a multiplicative group and define the set $S = \mathbb{N}g_1 + ... \mathbb{N}g_n$. Define multiplication in $S$ by expanding the product $(a_1 g_1 + ... a_n g_n)(b_1 g_1 + ...
5
votes
3answers
161 views

Does $p\mid f(m)+f(n)\leftrightarrow p\mid f(m+n)$ imply $f(m+n)=f(m)+f(n)$?

Let $f:\mathbb{N}\to\mathbb{N}$ be a function such that: $$(\forall p: \mathrm{~prime~})(\forall m,n\in\mathbb{N})(p\mid f(m)+f(n)\leftrightarrow p\mid f(m+n))$$ is $f$ linear? by linear I mean: ...
1
vote
1answer
52 views

Prove $p^n\ne a^3+b^3$ where $p\in\mathbb{P}\ge5$, $n,a,b\in\mathbb{N}$

Given prime $p\geq5$, prove that $p^n$ can't be represented as sum of two positive cubes for any $n\in\mathbb{N}$. What about $p=2$ and $p=3$?
15
votes
8answers
3k views

Prove that none of $\{11, 111, 1111,\dots \}$ is the perfect square of an integer

Please help me with solving this : prove that none of $\{11, 111, 1111 \ldots \}$ is the square of any $x\in\mathbb{Z}$ (that is, there is no $x\in\mathbb{Z}$ such that $x^2\in\{11, 111, 1111, ...
2
votes
2answers
57 views

Find all $a,b$ such that $\overline{a,b}=b/a$ where $(a,b)=1$ and $a,b\in\mathbb{N}$.

We are given $a$ and $b$ such that $(a,b)=1$ and $a,b\in\mathbb{N}$. If we write number $a$, then add a decimal point, and write number $b$ after it, we get a certain number $k$. If $k=b/a$, find ...
2
votes
3answers
95 views

Does $ab \equiv 0 \pmod n$ imply $n\mid a$ or $n\mid b$ if $n$ is prime?

I know that $ab \equiv 0 \pmod n$ does not imply $n\mid a$ or $n\mid b$ for regular $n$. When $n$ is prime can I use the fundamental theorem of arithmetic to say that $n\mid a$ or $n\mid b$ ? I am ...
0
votes
0answers
48 views

Prove that $\gcd(2^a-1,2^b-1)=2^{\gcd(a,b)}-1$ [duplicate]

Prove that $\gcd(2^a-1,2^b-1)=2^{\gcd(a,b)}-1$ Hints- $1$. Use Euclids Lemma $2$. $2^a=2^{a\%c}\mod (2^c)-1$ $3$. If $a=q\cdot b+c$ then $2^a=(2^c)^q\cdot 2^r$
0
votes
1answer
159 views

Using Prime numbers to map n integers uniquely to an integer x and allowing an easy reverse mapping

Say I have m integers: $i_{0}, i_{1}, ..., i_{x}, ..., i_{m} where -L < i_{x} < M$ where L and M are known integers is it possible to come up with a function that uses Primes that maps ...
0
votes
3answers
79 views

If $ab\equiv ac\pmod n$ and $a \not\equiv 0\pmod n$, then $b\equiv c\pmod n$ is true whenever $(a, n) =1$

If $ab$ is congruent to $ac \pmod n$ and $a$ is not congruent to $0 \pmod n$, then $b$ is congruent to $c \pmod n$. This was a homework problem and I was asked to show that this is false for some set ...
2
votes
2answers
115 views

How to prove that $+$ is commutative on the natural numbers?

Let $N$ be a non empty set. Let $s:N\to N$ a function satisfying: there is only one element in $N-s(N)$ (denoted by $1$); $s$ is injective; for any subset $X\subset N$, if $1\in X$ and $(n\in N ...
1
vote
2answers
108 views

Solutions for $x^2 \equiv 1 \pmod {2^k}$

What are the incongruent solutions for $x^2 \equiv 1 \pmod {2^k}$? I tested it with a couple small values and came up with the answer and proof. The answer is, if $k \ge 3, x \in ...
2
votes
3answers
164 views

Prove that $(n, n + 1) = 1$ for all $n \gt 0$. [closed]

I was thinking of doing this by contradiction. So by supposing: $$(n, n + 1) \neq 1$$ Then trying to to show that $(n, n + 1) \gt 1$ or $(n, n + 1) \lt 1$. But I'm not sure how I can accomplish ...