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

learn more… | top users | synonyms

3
votes
2answers
207 views

Prove that if perfect squares divide each other, then so do the originals - without primes

I want to prove: $$\text{If }a^2|z^2,\text{ then }a|z.$$ Assume everyone is a positive integer, etc. Unless I'm deluding myself, this is pretty easy to show using unique prime factorization. But I ...
2
votes
2answers
240 views

smallest positive number

How to find the smallest positive number $x$ such that $2011x^{2}+1$ is a square number $$ 2011x^{2}+1=y^{2} $$ $x,y$ are positive numbers
1
vote
5answers
97 views

polynomial of degree at least 1

I was told to assume $f(x)$ is a polynomial with degree $d\geq 1$ with integer coefficients and positive leading coefficient. (i) I need to show that there are infinitely many $x$ such that $f(x)$ ...
2
votes
1answer
278 views

Existence of an irreducible polynomial over $\mathbb F_p$. [duplicate]

Possible Duplicate: Lack of understanding of the proof of the existence of an irreducible polynomial of any degree $n \geq 2$ in $\mathbb{Z}_p[x]$ Existence of irreducible polynomials over ...
0
votes
2answers
72 views

Computing recurrences

This is probably a very simple to solve question, but i do not know how to use Pari gp to find the succesive $z(n)$ and $y(n)$ values of , for instance, the recurrence : ...
3
votes
2answers
491 views

Product of sums of square is a sum of squares.

Given $a,b,c,d \in \mathbb{Z}$, there is $x,y$ such that $$(a^2 + b^2)(c^2 + d^2) = x^2 + y^2$$ One can show this by considering the complex number $a + bi$ and $c+ di$, using complex properties to ...
13
votes
3answers
532 views

How can I calculate $\sin\left(10^{10^{100}} - 10\right)^\circ$?

How can I calculate the sine of a googolplex minus 10 degrees?
0
votes
1answer
148 views

Can all Venn diagrams be constructed?

I have a question that relates to this question about Venn diagrams. Has anyone shown that all Venn diagrams can (theoretically) be constructed?
5
votes
5answers
3k views

What is the norm of a complex number?

I'm in a number theory class and I'm trying to understand what the norm is... For some complex number $Z = a +bi$, $Z$ times the conjugate of z is equal to $(a^2)+(b^2)$. Most of what I've read about ...
2
votes
3answers
416 views

Prove or disprove that $a$ and $b$ are coprime integers iff $a^2$ and $b^2$ are coprime integers

Prove or disprove: $\forall a,b\in \mathbb N $, $a$ and $b$ are coprime integers IFF $a^2$ and $b^2$ are coprime integers. I know how to prove that if $a$,$b$ are coprime integers but I have no clue ...
0
votes
3answers
68 views

Number Theory: Product of Power of Two

I'm having trouble solving the following number theory problem in my textbook: Let a $\in Z$ with $a > 0$. Prove that there exists $k, n \in Z$ with n odd such that $a = 2^k n$ So far I've ...
0
votes
2answers
3k views

Negative Ratio - Is it possible

I came across this problem recently where $A:b = C:A$ and $B= -9$ and $C = -4$ What is $A$ then? I got $A^2 = 36$ $\Rightarrow$ $A= \pm 6$ However, as far as my knowledge goes a ratio is always ...
48
votes
9answers
3k views

The last digit of $2^{2006}$

My 13 year old son was asked this question in a maths challenge. He correctly guessed 4 on the assumption that the answer was likely to be the last digit of $2^6$. However is there a better ...
2
votes
0answers
48 views

Proving a number is a carmichael number [duplicate]

Possible Duplicate: How do I prove $n$ is a Carmichael number? I am trying to verify the fact that $1729$ is a Carmichael number. However, a number $n$ is a carmichael number if and only if ...
2
votes
1answer
72 views

Powers of a greatest common denominator [duplicate]

Possible Duplicate: Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$ Given $n \ge 1$ and $s, t \in \mathbb{Z}^{+}$, $s \ge t$, prove that $$\gcd(n^{s} - 1, n^{t} - 1) = ...
5
votes
3answers
346 views

Are there arbitrarily long prime deserts? [duplicate]

Possible Duplicate: What is the maximum number of consecutive composite numbers possible? Define a prime desert of length $k$ to be a sequence of numbers $n + 1, n + 2, ..., n + k $ such ...
3
votes
3answers
1k views

If a and b are relatively prime and ab is a square, then a and b are squares.

I need to prove this statement, so I would like someone to critique my proof. Thanks Since $ab$ is a square, the exponent of every prime in the prime factorization of $ab$ must be even. Since $a$ ...
3
votes
0answers
148 views

Must be rational number

Let $a$, $b$ positive rational number. Suppose that there exist two odd positive integers $p$, $q$ such that $\sqrt[p]{a}+\sqrt[q]{b}$ is rational. Prove that both $\sqrt[p]{a}$ and $\sqrt[q]{b}$ are ...
2
votes
1answer
1k views

Can we identify the largest product of two numbers made from four given digits

My problem is, given 4 positive integers (single digits 0-9), is there a generic way to identify which combination of them will yield the largest product of a single multiplication? So to clarify if ...
7
votes
3answers
203 views

If the set of primes where $p$, $p+2$ is infinite, would this imply that the set of $p$ and $p+2n$ is also infinite?

If the set of primes $p$ such that $p+2$ is also prime is infinite, would this imply that the set of primes such that $p+2n$ where $n$ is any positive integer for each pair is also infinite?
0
votes
0answers
79 views

Floor function within a congruence

In essence, the floor function is causing problems. Is there any way to get the inner linear expression, outside of the floor function? $\lfloor(a_1x_1+...+a_nx_n)/d\rfloor \equiv b\pmod m$, for ...
3
votes
2answers
195 views

Computing $n$ such that $\phi(n) = m$

Is there a general procedure for computing an inverse of the euler totient function? I did find an old SE post that seemed to have some pointers -How to solve the equation $\phi(n) = k$? However, I ...
1
vote
1answer
197 views

Euclid's Proof of infinite prime numbers

I think this should probably be obvious, but I having trouble understanding part of the proof: If $N=p_1p_2\cdots p_n+1$, then why is it necessarily true that any given $p$ does not divide $N$?
3
votes
1answer
56 views

When does a solution to $a^x\equiv b\pmod m$ exist, and how is the smallest solution denoted?

Given fixed integers $a,b,m$ such that $\gcd(a,m)=1$, how do I know if there exists an integer $x$ such that $a^x\equiv b\text{ mod } m$, also if a solution does exist, what is the typical notation ...
6
votes
5answers
652 views

Problem with congruence relations

Show that $97|2^{48}-1$ So far I managed to use Fermat's Little Theorem where I got $2^{96}≡1\pmod {97}$ Which I then reconstructed as $2^{48}*2^{48}≡1\pmod {97}$ And I got stuck here. I'm pretty ...
3
votes
3answers
364 views

finding the first odd abundant number less than $1000$

We say about number $n $ abundant if the sum of the divisors except $n$ is bigger than the number $n$.For example : $12$ is abundant because the sum of divisors except $12$ is bigger than $12$ : ...
1
vote
1answer
81 views

Solutions of $\prod\limits_{i=1}^{2011}{S(n+i)}=S(n)^{2011}$

Let $S(k)$ be the sum of digits of natural number $k$. Is there $n\in\Bbb N$ such that $$ \prod_{i=1}^{2011}{S(n+i)}=S(n)^{2011}?$$ All I could get is, since $2011=223\cdot9+4$ we have at least ...
0
votes
1answer
40 views

Finding a generating set

I have a subspace of $Z^3$, $N=\{(x,y,z)\in Z^3| 2x+3y-5z=0\}$. How to find the generating set for $N$. I tried to solve it for $z$ but then my generating set is not in $Z^3$.
2
votes
0answers
65 views

basic number theory question (gcd) [duplicate]

Possible Duplicate: Largest integer that can’t be represented as a non-negative linear combination of $m, n = mn - m - n$? Why? Q: Suppose $u$ and $v$ are positive integers, and $k$ a ...
6
votes
3answers
598 views

number of multiples of 4 that are multiples of 4 even if you permute their digits

How many 4 digit numbers are multiples of 4 no matter how you permute them? (base 10)
9
votes
4answers
884 views

Induction Proof that $x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1})$

This question is from [Number Theory George E. Andrews 1-1 #3]. Prove that $$x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1}).$$ This problem is driving me crazy. $$x^n-y^n = ...
4
votes
4answers
163 views

Is the length of a segment between 0 and 1 exactly 1?

What is the length of the line segment between points A and B on a number line, where A = 0 and B = 1? Is it exactly 1? Perhaps I am thinking about it in an incorrect manner, but it seems to me that ...
0
votes
0answers
55 views

Large Numbers Divisibility

Does $2^{2^{2011} + 1}$ divide $2^{2^{2012}} - 1$? Is my solution correct? Consider the ratio: $$ \frac{2^{2^{2012}} - 1}{2^{2^{2011}} + 1} = \frac{2^{2^{2011} \cdot 2^1} - 1}{2^{2^{2011}} + ...
2
votes
3answers
103 views

Quadratic Residues Are Distinct

I'm having a little trouble understanding the proof that the quadratic residues mod p, given by: $1^2,2^2,...,(\frac{p-1}{2})^2$ are distinct. So far I have this: If we have $j$ such that ...
0
votes
2answers
80 views

What is the largest possible product of those $3$ number?

Suppose $n$ is a positive integer and $3$ arbitrary numbers are choosen from the set $\{ 1,2,3, \cdots , 3n+1 \}$ with their sum equal to $3n+1$. What is the largest possible product of those $3$ ...
3
votes
2answers
104 views

Forms $apq +b = r^{n} $ where p,q,r are primes

Some small results for $2pq +3 = r^{n} $ p,q,r primes; written in the form (p,q,r,n): $(3,1093,3,8) (59,997,7,6) (73,107,5,6) (7,223,5,5) (3,13,3,4) (11,109,7,4) (109,131,13,4) (277,1667,31,4) ...
2
votes
2answers
68 views

How to solve for these simultaneous equations

I have the following set of equations $$\pi_1 = \pi_3 + [1 - \alpha(1 - p)]\pi_4$$ $$\pi_2 = \alpha(1 - p)\pi_4$$ $$\pi_3 = \alpha(1 - p)]\pi_1$$ $$\pi_4 = [1 - \alpha(1 - p)]\pi_1 + \pi_2$$ $$\pi_1 ...
3
votes
1answer
134 views

Wilson's theorem

Can you hint me on how to show that $2(p-3)!\equiv -1\pmod{p}$, for $p>2$ prime. I that Wilson's theorem says that $(p-1)!\equiv-1\pmod{p}$, and that $(p-3)!=(p-3)(p-2)(p-1)!$, but I'm not seeing ...
9
votes
1answer
529 views

Which families of groups have interesting formulas for the number of elements of given order?

Suppose that $G$ is a group and that $n$ is a positive integer diving the order of $G$. Let $f_n(G)$ be the number of elements satisfying $x^n = 1$ in $G$. According to a theorem of Frobenius, then we ...
1
vote
1answer
101 views

Solutions to easy Diophantine $8pq +1 = a^{2}$, p and q primes

Show that $p = 3$ and $p = 5$ are the only primes with a maximal $3$ solutions each to $8pq + 1 = a^2$, where $p$ and $q$ are prime.
0
votes
3answers
153 views

solving a linear Diophantine equation

How to show that there exist non-negative integers $x,y$ such that $ax+by=ab+k$ where $a,b$ are co-prime whole numbers is true for all non zero integers $k$. PS: Sorry for missing the key ...
4
votes
0answers
87 views

Polynomial bound

Let $P(x)=a_4 x^4+a_3 x^3+a_2 x^2+a_1 x+a_0$ such that $$\forall i\in \{0, 1, 2, 3, 4\};\phantom{;}a_i\in\mathbb{Z} \wedge |a_i|\leq T\phantom{.}(T\in\mathbb{Z}^+ )$$ Suppose that $P(x)> 0$ for all ...
5
votes
3answers
106 views

Given $N$, find $ab = N$ with $a$ and $b$ as close as possible

Given a number $N$ I would like to factor it as $N=ab$ where $a$ and $b$ are as close as possible; say when $|b-a|$ is minimal. For certain $N$ this is trivial: when $N$ is prime, a product of two ...
4
votes
2answers
115 views

Legendre symbol question

Given an integer $N \geq 2$, are there infinitely many integers $d$ such that the Legendre symbol $(\frac{d}{p}) = 1$ for all prime $p \leq N$?
4
votes
2answers
165 views

$n +1$th Fibonacci number modulo $n$

The Pisano period studies the $n$th Fibonacci number $F_{n}$ modulo $n$. Is there anything about $F_{n + 1} \pmod n$?
3
votes
1answer
61 views

Counting all multiples of $n_1$ in the vicinity of $n_2\pm1$.

Consider the following graphic: The points on the upper line, "the $12$ line", are $12$ apart while the ones on the lower line, "the $5$ line", are $5$ apart. The points on the upper line progress ...
2
votes
2answers
213 views

Square roots of unity modulo (N/f)^2

My question relates to square roots of unity modulo N, ie $r^2 = 1 \mod N$. I have an efficient algorithm for obtaining these for arbitrary $N$. But for a given $N$ what I really want is to obtain ...
2
votes
0answers
160 views

Partition minimizing maximum of Euler's totient function across terms

Given natural numbers $M$ and $N$, I'd like to find a partition of $2^N$ with $M$ or fewer terms, $t_1 + t_2 + ... + t_M$, such that $\max(\phi(t_1), \phi(t_2), ..., \phi(t_M))$ is minimized, where ...
10
votes
2answers
143 views

Permuting elements of a set around a circle

Given $15$ objects placed around a circle, is it possible to permute their order such that the distance between any two elements is different in the second permutation from that in the original state? ...
0
votes
1answer
43 views

Counting instances where $bn_k$ is equal to any $an_k-1$ or $an_k+1$ under a given number on a number-line.

If I let $a, b$, and $n$ be integers greater than $0$ and I incrementally and consecutively plot $a{n}-1$ and $a{n}+1$ on a number-line such that when $a=2$ , I plot points { $2n_1-1, 2n_1+1$, ...