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

learn more… | top users | synonyms (1)

0
votes
1answer
1k views

Proofs of the properties of Jacobi symbol

The definition and properties of Jacobi symbol are stated in this article. I don't have a textbook handy containing the proofs of the following properties of Jacobi symbol. It seems to me that not ...
5
votes
1answer
177 views

Making $x+\frac1y$, $y+\frac1z$, and $z+\frac1x$ all integer.

Let $x,y,z\in\Bbb R$, and at least one is be a postive integer, and such that $$x+\frac{1}{y},\;y+\frac{1}{z},\;z+\frac{1}{x}\in\Bbb Z$$ Find the value of $x,y,z$. My try: ...
1
vote
3answers
1k views

A perfect square and a perfect cube: is it also a perfect sixth power?

As the title suggests: Prove that for any natural number, if it is a perfect square and a perfect cube, it is also a perfect sixth power. For some reason I just have hit a road block on this ...
3
votes
2answers
105 views

Can we have $x^3 \equiv 1 \pmod n$?

For $n \geq 5$ can we have $x^3\equiv 1 \pmod n$. And if so for what $n$? I was thinking that we need $x^2 \equiv x^{-1}$ but I cant see when thats possible if possible. Regards.
1
vote
2answers
151 views

Let p, q, r be distinct primes greater than 3, and let n = pqr.

Show that if $x \in \mathbb{Z}$ satisfies $x^{2} \equiv 9\mod{n}$ then $x \equiv ±3 \mod{p}$, $x \equiv ±3 \mod{q}$ and $x \equiv ±3 \mod {r}$. I'm not sure what to do. Any help is ...
1
vote
1answer
79 views

On a Congruence Relation Between Polynomials

Problem: If $ f \in \mathbb{Z}[X] $ and $ f(a) ≡ 0 \pmod n $ for some $ a \in \mathbb{Z} $, then there exists a $ g \in \mathbb{Z}[X] $ such that $ f(X) ≡ (X − a) g(X) \pmod n $. I think that ...
0
votes
0answers
88 views

Suppose a and b are two relatively prime numbers. Then what are the possible values of $\gcd (a + b,a ^2 + b ^2 )?$ [closed]

Suppose a and b are two relatively prime numbers. ie $\gcd(a , b) = 1.$ Then what are the possible values of $\gcd (a + b,a^2 + b^2 ) ?$
2
votes
1answer
96 views

Solve for n: $\varphi(2n)=\varphi(3n)$

I know the following: $$\varphi(2n)=\varphi(2)\varphi(n)=\varphi(n)\iff(2,n)=1$$ And $$\varphi(3n)=\varphi(3)\varphi(n)=2\varphi(n)\iff(3,n)=1$$ But now I'm not sure what to do with this info.
2
votes
2answers
215 views

Solving two simultaneous equations

Suppose that $x$, $y$ and $z$ are three integers (positive,negative or zero) such that we get the following relationships simultaneously $x + y = 1 - z$ and $x^3 + y^3= 1 - z^2$ Find all such ...
2
votes
1answer
99 views

Proof using Chinese Remainder Theorem for $n=p_1^{m_1}\cdot p_2^{m_2}\cdots p_k^{m_k}$

I wish to find an expression for the number of solutions $x$ to $x^2\equiv 9 \pmod n$, with $x$ a natural number${}<n$, when $n$ has a factorization $n=p_1^{m_1}\cdot p_2^{m_2}\cdots p_k^{m_k}$ ...
11
votes
2answers
489 views

How does one attack a divisibility problem like $(a+b)^2 \mid (2a^3+6a^2b+1)$?

In my current line of investigation, I am running into [many] divisibility questions like the one in the title, i.e. $$ (a+b)^2 \mid (2a^3+6a^2b+1), \qquad(\star) $$ where $a > b \ge 1$ are ...
0
votes
1answer
40 views

A semiprime only has $4$ factors

It seems quite trivial, but I can't figure out how to explain that in general a semiprime $pq$ only has $4$ factors (namely $1, p, q, pq$). Can anyone give me a small proof?
1
vote
2answers
183 views

If $a, b, c$ are integers with $a^2 + b^2 = c^2$, then $a$ and $b$ cannot both be odd [closed]

If $a, b, c$ are integers with $a^2 + b^2 = c^2$, it's true that $a$ and $b$ cannot both be odd. But how can we prove it
-1
votes
1answer
77 views

Symbol Jacobi equality

Let $p$ be an odd prime, $a>0$ and $p \nmid a$. Show that the following equality holds for the Jacobi symbol $$ \left(\frac{a}{p}\right)=\left(\frac{a}{p-4a}\right) $$ Hint: Derive the ...
3
votes
2answers
160 views

Show that if $F$ is multiplicative, then $f$ is multiplicative

Suppose that $F(n) = \sum_{d\mid n} f(d)$ for all $n$. Show that if $F$ is multiplicative, then $f$ is also multiplicative. I'm sorry for my weird notation. I'm not used to this type of syntax but ...
1
vote
1answer
119 views

Prove that there exists only 2 solutions for $x^2 \equiv 9 \pmod {p^k}$, ($p$ an odd prime > 3 and $x$ a natural number < $n$)

It appears that the only two solutions are always $3$ and $p^k-3$, I want to prove this, here has been my approach, I think I am close but just missing something, would really appreciate any help!!! ...
1
vote
5answers
87 views

Find the natural numbers $a$ and $b$ so that $a\cdot b$ has the largest possible value but $a + b = x$ must hold.

Is there a way to find the natural numbers $a$ and $b$ so that $a\cdot b$ has the largest possible value but $a + b = x$ must hold. It's easy small numbers but is there any way, through calculus or ...
0
votes
3answers
52 views

Is this a valid representation of last digit $7^{2013}$

As we are looking at $\Z_{10}$ or $\pmod{10}$ we can redefine this as}$$7^{2013} = 7^{2\cdot 1006}\cdot 7 = 7^2(7^{1006})\cdot 7=[-3^{2}]^{1006} \cdot 7=[1]\cdot 7=7$$
0
votes
1answer
59 views

Prove that for $n=2^k$, $(k \ge 3)$ there are 4 natural numbers less than $n$ that satisfy $b^2 \equiv 9 \pmod n$.

I think I am close to proving this, but just need a bit of help with some gaps in my understanding. I found using a recursive function in a small program that it seemed that for $k \ge 3$, I always ...
1
vote
1answer
31 views

Index relation between two primitive roots

Let n be a positive integer, and x an integer such that gcd(n, x)=1. Suppose g and h are primitive roots mod n. Show that: $ind_{h}(x) = ind_{h}(g) \cdot ind_{g}(x) (mod {\phi}(n))$ I've been ...
0
votes
1answer
65 views

Solve: $ \dfrac{x}{k_1} + \dfrac{y}{k_2}=z $ when $ x+y \neq z$

If $\gcd(x,y,z)>1$, any hint on how to find all the non-zero pairs $(k_1, k_2) \in \mathbb{Z^2} $ such that $ \dfrac{x}{k_1} + \dfrac{y}{k_2}=z $ when $ x+y \neq z$?
2
votes
5answers
217 views

Proof of $10^{n+1} -9n -10 \equiv 0 \pmod {81}$

I am trying to prove that $10^{n+1} -9n -10 \equiv 0 \pmod {81}$. I think that decomposing into 9 and then 9 again is the way to go, but I just cannot get there. Any help is greatly appreciated. ...
4
votes
1answer
106 views

Congruences with prime number and factorial

Prove that if $p\equiv 1 \pmod{4}$ is a prime number and $$x\equiv \pm \left(\frac{p-1}{2}\right)! \pmod{p}$$ then $x^2\equiv -1 \pmod{p}$ I think Wilson's theorem will come in handy here, used ...
0
votes
1answer
64 views

Demonstration of complete system of residual classes. (Demonstração de sistema completo de classes resíduais.)

Which step I have to follow to solve: Let $ \{a_1, ..., a_m\} $ a complete system of residues modulo $m$, show that $a\in\mathbb{N}$, then $ \{a_1 + a, ..., a_m + a\} $ is a complete residue ...
0
votes
3answers
50 views

Will modulus give me $n - 1$?

Say I divide a number by 6, will a number modulus by 6 always be between 0-5? If so, will a number modulus any number (N) , the result should be between $0$ and $ N - 1$?
4
votes
1answer
105 views

Exponential Diophantine Equation $3^x5^y-2^s7^t=1$.

How to solve $3^x5^y-2^s7^t=1$ completely? Does there exists any general techniques dealing with such exponential equations? For equations like $a^x-b^y=1$, Mihăilescu's theorem (Catalan conjecture) ...
1
vote
1answer
572 views

What is an “incongruent” solution?

For example, "Solve the congruence (if possible), listing all the incongruent solutions:" $$561x\equiv 3575\mod{1562}$$ I found $x\equiv 37+142t,\ 0\leq t\leq 10,\ t\in\mathbb{Z}$... There are 11 ...
3
votes
3answers
4k views

How can I list all numbers relatively prime to X? (but less than X)

Given a number X how can I find all (or most) numbers that are relatively prime to and less than X? Ideally I'd like this function to tell me the largest primes first.
1
vote
1answer
54 views

Show that $\frac{(m+n)!}{m!n!}$ is an integer whenever $m$ and $n$ are positive integers using Legendre's Theorem

Show that $\frac{(m+n)!}{m!n!}$ is an integer whenever $m$ and $n$ are positive integers using Legendre's Theorem. Hi everyone, I seen similar questions on this forum and none of them really talked ...
1
vote
2answers
566 views

Show that if $a$ and $b$ are positive integers with $(a,b)=1$ then $(a^n, b^n) = 1$ for all positive integers n [duplicate]

Show that if $a$ and $b$ are positive integers with $(a,b)=1$ then $(a^n, b^n) = 1$ for all positive integers n Hi everyone, for the proof to the above question, Can I assume that since $(a, b) = ...
1
vote
0answers
166 views

Peano system vs natural numbers

What exactly is the difference between natural numbers and an arbitrary peano system? In particular there is a proof in my book for recursion on natural numbers, as well as an erroneous proof of ...
0
votes
1answer
54 views

$\mod 4$ properties of Fermat number

Let $k\in\Bbb N$. Let $2^{2^k}+1$ be a composite Fermat number. Let $p$ be a prime factor of $2^{2^k}+1$. Then is $p\mod 4\equiv 1$?
-1
votes
1answer
427 views

Prove that if $\gcd(a,b)=1$, then $\gcd(a\cdot b,c) = \gcd(a,c)\cdot \gcd(b,c)$.

Let $a,b,c \in \mathbb{Z}$, prove that if $\gcd(a,b)=1$, then $\gcd(a\cdot b,c) = \gcd(a,c)\cdot \gcd(b,c)$.
0
votes
1answer
47 views

A small question in stochastic process(sth. related to number theory)

Let $J$ be a set of nonnegative integers whose greatest common divisor is $d$. And suppose that $J$ is closed under addition, then J contains all but a finite number of integers in the set $ \{ ...
1
vote
1answer
61 views

On divisors of Mersenne numbers

How can we prove that $M_n=2^n-1$ does not have any divisors between $\sqrt{3M_n}$ and $\sqrt{5M_n}$?
1
vote
2answers
55 views

field number theory question

If we have ${a+b\sqrt{-1}}$ for a,b in ${Z_p}$, with $p$ as an odd prime, with $\sqrt{-1}^2=-1$, how do we show that $a+b\sqrt{-1}$ has a multiplicative inverse iff $a-b\sqrt{-1}$ has a multiplicative ...
3
votes
3answers
180 views

Are there infinitely many $n$ for which $\varphi(n)$ is a perfect square?

Prove or disprove: $\phi(n)$ is a perfect square for only a finite number of odd numbers n. I know it works for even numbers since we can use $n=p^k$ and have $p=2$, however, I don't know about odd ...
0
votes
2answers
112 views

Find integer solutions

Find all integer solutions to the following: $2x+10y-11z=1$ $x-6y+14z=2$ I am not quite sure how to do this... I know I will get equations in the end with each variable expressed in terms of ...
1
vote
2answers
71 views

Is this an acceptable congruency proof?

I have a past exam question that I proved as follows: $$(\forall n\in \Bbb Z)\bigl((3n^2-5\equiv 2 \pmod 4)\lor(3n^2-5\equiv 3 \pmod 4)\bigr)$$ If odd: $$3n^2 - 7 = k4,k\in \mathbb Z$$ $$3(2l+1)^2 - 7 ...
3
votes
5answers
184 views

Cyclic groups question

Show that $\mathbb Z_{35}^\times$ is not cyclic. I assume that I need to show that no element of $\mathbb Z_{35}$ has a particular order, indicating it is not cyclic, but I'm not sure how to do this. ...
1
vote
1answer
417 views

Show that if $a$ is an even integer and $b$ is an odd integer then $(a, b) = (a/2, b)$

Show that if $a$ is an even integer and $b$ is an odd integer then $(a, b) = (a/2, b)$ Hi everyone, I would like to know if my assumption is justified for answering the above question. Any ...
2
votes
3answers
126 views

number theory proof

Does this proof work? Prove or disprove that if $\sigma(n)$ is a prime number, n must be a power of a prime. Since $\sigma(n)$ is prime, $n$ can not be prime unless it is the only even prime, $2$, ...
2
votes
1answer
82 views

Are algebraic properties consistent among ALL types of number groups?

I'm embarking on a self study course of group theory, modular arithmetic, and other mathematics relating to cryptography. I notice that when studying modular arithmetic that they explicitly say that ...
1
vote
1answer
133 views

Wilson's Theorem Question

Show that $(p-1)!\equiv 2p-p^2$ with Wilson's Theorem. Wilson's theorem states that $(p-1)!\equiv -1\pmod p$. I tried working off of that to get $(p-1)!\equiv -1\pmod p$ $\Rightarrow (p-1)!\equiv ...
3
votes
0answers
454 views

Show that if both a, b are even integers not both 0, then $(a, b) = 2 (a/2, b/2)$

Show that if both a, b are even integers not both 0, then $(a, b) = 2 (a/2, b/2)$. Hi there, I want to know if the following proof I have is strong enough, or if I'm making false assumptions :|. ...
2
votes
0answers
94 views

Let n be a nonzero integer and p an odd prime not dividing n.

$p/(x^2+ny^2)$ for $x$, $y$ relatively prime $\Leftrightarrow$ to $(\frac{-n}{p})=1$. I have proved the "$\Rightarrow$" part by using the fact that $y$ and $p$ must be relatively prime, which implies ...
2
votes
3answers
179 views

Existence of positive integer k that are both squares

Is there a positive integer k such that $4k+1$ and $9k+1$ are both squares?
6
votes
2answers
99 views

On primes between $k$ and $k!$

I have the following homework question: "Show that for $k\geq 4$ between $k$ and $k!$ there always exists a prime number of the form $4n+3$." How can one prove it?
5
votes
3answers
84 views

Homomorphism defined by a function

Let $f: \mathbb{Z}_{143} \to\mathbb Z_{11} \times\mathbb Z_{13}$ be an homomorphism and define $f$ by $f(x) = (x\mod11, x \mod13).$ Determine an $x\in \mathbb{Z}_{143}$ such that $f(x) = (7,4).$ ...
2
votes
1answer
143 views

Identifying Ways of Dividing an Area into Merged Regions

Suppose an area is divided into N irregular regions. Unless N is very small there will be many ways in which a new division of the area can be obtained by merging adjacent regions. I want to ...