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

learn more… | top users | synonyms

5
votes
1answer
169 views

Typo in Marcus' $\textit{Number Fields}$?

I am doing Problem 5.10 of Marcus where it is given that $m$ is a square-free negative integer and that $\mathcal{O}_K$ is a PID where $K = \Bbb{Q}(\sqrt{m})$. Now in part (b) of this problem he ...
9
votes
2answers
3k views

Number of zero digits in factorials

Here is a riddle someone has been asked in a job interview: How many zero digits are there in $100!$? Well, I found the first $24$ quite fast by counting how many times five divides $100!$ ($5$ ...
1
vote
2answers
3k views

Prove that between every rational number and every irrational number there is an irrational number.

I have gotten this far, but I'm not sure how to make it apply to all rational and irrational numbers.... BTW, I'm quite newbish so please explain your reasoning to me like I'm 5. Thanks! UPDATE: ...
2
votes
5answers
284 views

How would one find other real numbers that aren't in the rational field of numbers?

For example, $\sqrt2$ isn't a rational number, since there is no rational number whose square equals two. And I see this example of a real number all the time and I'm just curious about how you can ...
0
votes
1answer
101 views

Nice sequences related to the Diophantine equation $d^{m+1} =a^{m}+ b^{m}+ c^{m}$

$$1, 3, 12, 32,...$$ Above is the sequence of the number of solutions, if there are, to the Diophantine equation : $d^{m+1} =a^{m}+ b^{m}+ c^{m}$ for $m =2$, in positive integers where $a, b$ and ...
4
votes
2answers
126 views

selecting an arbitary digit from an integer

Let us say I have an integer of an arbitrary length such as: $209484250490600018105614048117055336$ Is there an elegant function which allows me to select the $n$-th digit such that: $f(1) = 6$ ...
3
votes
0answers
498 views

Show if a product of coprime numbers is a perfect square, so are the numbers - without FTA

I want to prove: $$\text{If }\gcd(a,b)=1\text{ and }ab=n^2,\text{ then }a,b\text{ are also perfect squares.}$$ Assume everyone is a positive integer, etc. Unless I'm deluding myself, this is pretty ...
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
490 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
531 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
414 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
343 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
593 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
873 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 ...